fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define sp " "
  5. #define el '\n'
  6. #define ll long long
  7. vector<vector<int>> adj;
  8. vector<int> vis;
  9. int ans = 0;
  10. void dfs(int s){
  11.     ans++;
  12.     vis[s] = 1;
  13.     for(auto u : adj[s]){
  14.         if(!vis[u])
  15.             dfs(u);
  16.     }
  17.  
  18. }
  19. void Solution()
  20. {
  21.     int n, m;
  22.     cin >> n >> m;
  23.     adj = vector<vector<int>> (n+1);
  24.     vector<vector<int>> v;
  25.     for(int i = 0; i < m; i++){
  26.         int k; cin >> k;
  27.         vector<int> a(k);
  28.         for(int j = 0; j < k; j++){
  29.             cin >> a[j];
  30.         }
  31.         v.push_back(a);
  32.     }
  33.  
  34.     for(int i = 0; i < m; i++){
  35.         for(int j = 0; j < v[i].size(); j++){
  36.             if(j > 0) 
  37.                 adj[v[i][j]].push_back(v[i][j-1]);
  38.             if(j < (v[i].size()-1))
  39.                 adj[v[i][j]].push_back(v[i][j+1]);
  40.         }
  41.     }
  42.     vis.assign(n+1,0);
  43.     map<int,int>mp;
  44.     for(int i = 1; i <= n; i++){
  45.         if(!vis[i]){
  46.             dfs(i);
  47.             mp[i] = ans;
  48.             ans = 0;
  49.         }
  50.     }
  51.     for(int i = 1; i <= n; i++){
  52.         for(int j = 0; j < adj[i].size(); j++){
  53.             if(!mp[adj[i][j]]) 
  54.                 mp[adj[i][j]] = mp[i];  
  55.         }
  56.     }
  57.     for(auto u : mp){
  58.         cout << u.second << sp;
  59.     }
  60.     cout << el;
  61. }
  62. int main()
  63. {
  64.     ios::sync_with_stdio(0);
  65.     cin.tie(0); cout.tie(0);
  66.     int t;
  67.     // cin >> t;
  68.     // for(int tc = 1; tc <= t; tc++)
  69.         Solution();
  70.     return 0;
  71. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/f6zdAr
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
14 hours ago

					

					

						
visibility:

						

							 public																												
							
							

								
							

						

					

										
										

					
					 Share or Embed source code
					
					
					
					

						
						
						
						
						
						
						
					

					
						
	
	
	
	
					
					
					
					
					 
					
					
					
					 
					
					
					
					
					
					

					

					

					
						
					

					


	
Discover > Sphere Engine API

	
The brand new service which powers Ideone!

	
	
Discover > IDE Widget

    
Widget for compiling and running the source code in a web browser!