In this HackerEarth Boruto and Dojutsu problem solution Boruto subconsciously awakened a Dojutsu (magic) in his right eye which has a lot of special powers. One of its powers includes the ability to track a target through its chakra (energy). One day while training, Boruto marks N targets, each of which has some color Ai. Some of the targets are connected to each other, as a result of which these N targets form a colorful undirected graph G with N nodes (denoting the N targets), indexed from 1 to N and M edges (denoting the M connections between the targets), indexed from 1 to M.
Using the power of his eye, Boruto was able to find the number of distinct colors in the connected component containing any particular target. Now Boruto wants to know the number of distinct colors in the connected component containing any particular target if the connections between the targets are being removed dynamically. As he is at an early stage of learning how to use Dojutsu, he wants your help in getting the answer to this problem.
HackerEarth Boruto and Dojutsu problem solution.
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <math.h>
#define ll long long int
#define maxN 100000
#define maxVal 100000000
#define minVal -100000000
#define mod 1000000007LL
#define gcd(a,b) __gcd(a,b)
using namespace std;
struct edge
{
int u,v;
};
struct operations
{
int c,i;
};
int n,m,q;
int a[maxN+5];
edge ed[maxN+5];
int parent[maxN+5];
int val[maxN+5][105];
operations qu[maxN+5];
int mark[maxN+5]={0};
int ans[maxN+5];
void makeNode(int i,int x)
{
int j;
for(j=0;j<=100;j++)
val[i][j]=0;
val[i][x]=1;
}
int get(int i)
{
if(i!=parent[i])
parent[i]=get(parent[i]);
return parent[i];
}
void combine(int u,int v)
{
int x,y,i;
x=get(u);
y=get(v);
if(x!=y)
{
for(i=0;i<=100;i++)
val[y][i]+=val[x][i];
parent[x]=y;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int i,j;
cin>>n>>m>>q;
for(i=1;i<=n;i++)
{
cin>>a[i];
parent[i]=i;
makeNode(i,a[i]);
}
for(i=1;i<=m;i++)
cin>>ed[i].u>>ed[i].v;
for(i=1;i<=q;i++)
{
cin>>qu[i].c>>qu[i].i;
if(qu[i].c==1)
mark[qu[i].i]=1;
ans[i]=-1;
}
for(i=1;i<=m;i++)
if(!mark[i])
combine(ed[i].u,ed[i].v);
for(i=q;i>=1;i--)
if(qu[i].c==1)
combine(ed[qu[i].i].u,ed[qu[i].i].v);
else
{
qu[i].i=get(qu[i].i);
ans[i]=0;
for(j=0;j<=100;j++)
if(val[qu[i].i][j])
ans[i]++;
}
for(i=1;i<=q;i++)
if(ans[i]!=-1)
cout<<ans[i]<<"\n";
return 0;
}Second solution
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define be begin()
#define en end()
#define all(x) (x).begin(),(x).end()
#define alli(a, n, k) (a+k),(a+n+k)
#define REP(i, a, b, k) for(__typeof(a) i = a;i < b;i += k)
#define REPI(i, a, b, k) for(__typeof(a) i = a;i > b;i -= k)
#define REPITER(it, a) for(__typeof(a.begin()) it = a.begin();it != a.end(); ++it)
#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds
#define eps 1e-6
#define pi 3.141592653589793
using namespace std;
template<class T> inline T gcd(T a, T b) { while(b) b ^= a ^= b ^= a %= b; return a; }
template<class T> inline T mod(T x) { if(x < 0) return -x; else return x; }
typedef vector<int> VII;
typedef vector<ll> VLL;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef pair<int, PII > PPII;
typedef vector< PII > VPII;
typedef vector< PPII > VPPI;
const int MOD = 1e9 + 7;
const int INF = 1e9;
// Template End
const int MAX = 1e5 + 5;
int id[MAX], A[MAX], cnt[MAX];
bool color[MAX][105];
VPII edges, query;
bool e[2*MAX];
VII ans;
void init (int N) {
REP(i, 1, N+1, 1) {
id[i] = i;
color[i][A[i]] = 1;
cnt[i] = 1;
}
}
int root (int x) {
while (id[x] != x) {
id[x] = id[id[x]];
x = id[x];
}
return x;
}
void combine(int q, int p) {
cnt[q] = 0;
REP(i, 0, 105, 1) {
color[q][i] = color[p][i] | color[q][i];
cnt[q] += color[q][i];
}
}
void union1 (int u, int v) {
int p = root(u);
int q = root(v);
if (id[p] != id[q]) {
id[p] = q;
combine(q, p);
}
}
int main(int argc, char* argv[]) {
if(argc == 2 or argc == 3) freopen(argv[1], "r", stdin);
if(argc == 3) freopen(argv[2], "w", stdout);
ios::sync_with_stdio(false);
int n, m, q, u, v, x, y, p;
cin >> n >> m >> q;
assert(1 <= n and n <= 100000);
assert(1 <= m and m <= min(200000, n*n));
REP(i, 1, n+1, 1) {
cin >> A[i];
assert(1 <= A[i] and A[i] <= 100);
}
REP (i, 1, m+1, 1) {
cin >> x >> y;
assert(1 <= x and x <= n);
assert(1 <= y and y <= n);
assert(x != y);
edges.pb(mp(x, y));
}
REP (i, 0, q, 1) {
cin >> x >> y;
assert(1 <= x and x <= 2);
if (x == 1) {
assert(1 <= y and y <= m);
y--;
e[y] = true;
}
else {
assert(1 <= y and y <= n);
}
query.pb(mp(x, y));
}
init(n);
REP(i, 0, m, 1) {
if (e[i] == false) {
union1(edges[i].fi, edges[i].se);
}
}
REPI (i, q-1, -1, 1) {
x = query[i].fi;
y = query[i].se;
if (x == 1) {
u = edges[y].fi;
v = edges[y].se;
union1(u, v);
}
else {
p = root(y);
ans.pb(cnt[p]);
}
}
REPI(i, (int)ans.size()-1, -1, 1) cout << ans[i] << endl;
return 0;
}
0 Comments