decoder__'s blog

By decoder__, history, 2 months ago, In English,

Can someone give me a detailed solution for the problem https://codeforces.com/contest/1167/problem/C. Please don't refer the tutorial, I have already gone through it.

include<bits/stdc++.h>

using namespace std;

const int N = 1000043; vector g[N];

int color{n int siz[N]; int n, m; int cc = 0;

int dfs(int x) { if(color[x]) return 0; color[x] = cc; int ans = (x < n ? 1 : 0); for(auto y : g[x]) ans += dfs(y); return ans; }

int main() { scanf("%d %d", &n, &m); for(int i = 0; i < m; i++) { int k; scanf("%d", &k); for(int j = 0; j < k; j++) { int x; scanf("%d", &x); --x; g[x].push_back(i + n); g[i + n].push_back(x); } } for(int i = 0; i < n; i++) { if(!color[i]) { cc++; siz[cc] = dfs(i); } printf("%d ", siz[color[i]]); } }

What's the use of color[N], siz[N] and cc?

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Let me try :)

So you are given $$$n$$$ users and $$$m$$$ groups. Let's assume initially that $$$ith$$$ user's group has no friends, now while taking the input, you will be given first the number of people in the $$$ith$$$ group $$$k_i$$$ and then $$$k_i$$$ distinct users are listed which means all the users given belong to the same group. After reading the complete input you need to answer this query for each user. The query is How many numbers of people are present in the user $$$i$$$ group?

Approach: Since I see some sets(Groups) involved which are Disjoint, the natural thing that I would use is DSU. This DS can be used to compute the size of each user group which answers our query for a particular user. Read about DSU here

Code with some explanation