1167C. News Distribution

Правка en2, от decoder__, 2020-04-02 17:06:14

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский decoder__ 2020-04-02 17:06:14 725
en1 Английский decoder__ 2020-04-02 15:11:11 191 Initial revision (published)