decoder__'s blog

By decoder__, history, 2 months ago, ,

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?

• 0

 » 2 months ago, # |   0 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#include using namespace std; // maximum number of users const int maxn = 5e5 + 500; vector Parent(maxn), Rank(maxn), Size(maxn); // intialize user groups with just 1 element i.e itself void init(){ for(int i = 0; i < maxn; i++){ Parent[i] = i; Rank[i] = 0; Size[i] = 1; } } // This is used for finding the head or representative of a group which // has user v int find_root(int v){ if(v == Parent[v])return v; return Parent[v] = find_root(Parent[v]); } // unite two groups which has user u and user v bool unite(int u, int v){ u = find_root(u); v = find_root(v); if(u != v){ if(Rank[u] < Rank[v])swap(u, v); Parent[v] = u; if(Rank[u] == Rank[v])Rank[u]++; Size[u] += Size[v]; return true; } return false; } // Return the number of people in user u's group int user_size(int u){ return Size[find_root(u)]; } int main() { ios::sync_with_stdio(false); cin.tie(0); init(); int n, m; cin >> n >> m; for(int i = 0; i < m; i++){ int k; cin >> k; int user[k]; for(int i = 0; i < k; i++)cin >> user[i]; for(int i = 0; i < k - 1; i++)unite(user[i], user[i + 1]); } for(int i = 1; i <= n; i++)cout << user_size(i) << ' '; return 0; }