Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector<int> par(500005);
- vector<int> ran(500005);
- vector<int> gro(500005);
- void makeset(int n){
- for(int i=1;i<=n;i++){
- par[i] =i;
- ran[i] =0;
- gro[i] =1;
- }
- }
- int findPar(int i){
- if(i == par[i]) return i;
- return par[i] = findPar(par[i]);
- }
- void uni(int a,int b){
- a = findPar(a);
- b = findPar(b);
- if(a==b){
- return;
- }
- if(ran[a] < ran[b]){
- gro[b]+=gro[a];
- par[a] = b;
- }
- else if(ran[b] < ran[a]){
- gro[a]+=gro[b];
- par[b] = a;
- }
- else{
- if(a<b){
- gro[a]+=gro[b];
- par[b] = a;
- ran[a]++;
- }
- else{
- gro[b]+=gro[a];
- par[a] = b;
- ran[b]++;
- }
- }
- }
- vector<int> peopleGettingNews(int n, int m, vector<vector<int>> &a){
- makeset(n);
- for(int i=0;i<m;i++){
- int len = a[i][0];
- if(len!=0){
- int last=-1;
- for(int j=1;j<=len;j++){
- if(last == -1){
- last = a[i][j];
- }
- else{
- uni(last,a[i][j]);
- }
- }
- }
- }
- vector<int> res;
- for(int i=1;i<=n;i++){
- res.push_back(gro[findPar(i)]);
- }
- return res;
- }
- signed main() {
- int n,m;
- cin>>n>>m;
- vector<vector<int>> a(m);
- for(int i=0;i<m;i++){
- int size;
- cin>>size;
- a[i].push_back(size);
- for(int j=0;j<size;j++){
- int temp;
- cin>>temp;
- a[i].push_back(temp);
- }
- }
- vector<int> ans = peopleGettingNews(n,m,a);
- for(int i=0;i<n;i++){
- cout<<ans[i]<<" ";
- }
- cout<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment