fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 100;
  5.  
  6. vector<int> adj[MAXN];
  7. bool visited[MAXN];
  8. int disc[MAXN], low[MAXN], parent[MAXN];
  9. bool isArticulation[MAXN];
  10. int timer;
  11.  
  12. void dfs(int u, int n) {
  13.     visited[u] = true;
  14.     disc[u] = low[u] = ++timer;
  15.     int children = 0;
  16.  
  17.     for (int v : adj[u]) {
  18.         if (!visited[v]) {
  19.             children++;
  20.             parent[v] = u;
  21.             dfs(v, n);
  22.  
  23.             low[u] = min(low[u], low[v]);
  24.  
  25.             if (parent[u] == -1 && children > 1)
  26.                 isArticulation[u] = true;
  27.  
  28.             if (parent[u] != -1 && low[v] >= disc[u])
  29.                 isArticulation[u] = true;
  30.         } else if (v != parent[u]) {
  31.             low[u] = min(low[u], disc[v]);
  32.         }
  33.     }
  34. }
  35.  
  36. int main() {
  37.     int n;
  38.     cin >> n;
  39.  
  40.     string row;
  41.     for (int i = 0; i < n; ++i) {
  42.         cin >> row;
  43.         for (int j = 0; j < n; ++j) {
  44.             if (row[j] == '1') {
  45.                 adj[i].push_back(j);
  46.             }
  47.         }
  48.     }
  49.  
  50.     memset(visited, false, sizeof(visited));
  51.     memset(isArticulation, false, sizeof(isArticulation));
  52.     memset(parent, -1, sizeof(parent));
  53.     timer = 0;
  54.  
  55.     for (int i = 0; i < n; ++i) {
  56.         if (!visited[i])
  57.             dfs(i, n);
  58.     }
  59.  
  60.     set<int> typeB;
  61.  
  62.     for (int i = 0; i < n; ++i) {
  63.         if (isArticulation[i]) {
  64.             for (int neighbor : adj[i]) {
  65.                 if (!isArticulation[neighbor]) {
  66.                     typeB.insert(neighbor);
  67.                 }
  68.             }
  69.         }
  70.     }
  71.  
  72.     for (int city : typeB) {
  73.         cout << city << " ";
  74.     }
  75.     cout << endl;
  76.  
  77.     return 0;
  78. }
Success #stdin #stdout 0s 5260KB
comments (?)
stdin
copy 
45
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/mNxpcu
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
2 days 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!