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, res;
  9. int ans = 0, f = 0;
  10. void dfs(int s){
  11.     ans++;
  12.     vis[s] = 1;
  13.     for(auto u : adj[s]){
  14.         if(!vis[u]){
  15.             if(f) res[u] = res[s];
  16.             dfs(u);
  17.         }
  18.     }
  19. }
  20. void Solution()
  21. {
  22.     int n, m;
  23.     cin >> n >> m;
  24.     adj = vector<vector<int>> (n+1);
  25.     vector<vector<int>> v;
  26.     for(int i = 0; i < m; i++){
  27.         int k; cin >> k;
  28.         vector<int> a(k);
  29.         for(int j = 0; j < k; j++){
  30.             cin >> a[j];
  31.         }
  32.         v.push_back(a);
  33.     }
  34.  
  35.     for(int i = 0; i < m; i++){
  36.         for(int j = 0; j < v[i].size(); j++){
  37.             if(j > 0) 
  38.                 adj[v[i][j]].push_back(v[i][j-1]);
  39.             if(j < (v[i].size()-1))
  40.                 adj[v[i][j]].push_back(v[i][j+1]);
  41.         }
  42.     }
  43.     res = vector<int> (n+1);
  44.     vis.assign(n+1,0);
  45.     map<int,int>mp;
  46.     for(int i = 1; i <= n; i++){
  47.         if(!vis[i]){
  48.             dfs(i);
  49.             res[i] = ans; 
  50.             ans = 0;
  51.         }
  52.     }
  53.  
  54.     vis.assign(n+1,0);
  55.     f = 1;
  56.     for(int i = 1; i <= n; i++){
  57.         if(!vis[i]){
  58.             dfs(i);
  59.         }
  60.     }
  61.     for(int i = 1; i <= n; i++){
  62.         cout << res[i] << sp;
  63.     }
  64.     cout << el;
  65. }
  66. int main()
  67. {
  68.     ios::sync_with_stdio(0);
  69.     cin.tie(0); cout.tie(0);
  70.     int t;
  71.     // cin >> t;
  72.     // for(int tc = 1; tc <= t; tc++)
  73.         Solution();
  74.     return 0;
  75. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/MqnK7H
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
12 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!