1167C. News Distribution

Revision en2, by decoder__, 2020-04-02 17:06:14

Can someone give me a detailed solution for the problem https://codeforces.me/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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English decoder__ 2020-04-02 17:06:14 725
en1 English decoder__ 2020-04-02 15:11:11 191 Initial revision (published)