fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector < vector < int > > grafo;
  5.  
  6. vector <int> d, low, parent;
  7.  
  8. vector<bool> cut, vis;
  9.  
  10. int tempo = 0, raiz = 0, x = 0;
  11.  
  12. void dfs(int v){
  13.  
  14. 	vis[v] = 1;
  15.  
  16. 	int children = 0;
  17.  
  18. 	low[v] = d[v] = tempo++;
  19.  
  20. 	vector <int> adj = grafo[v];
  21.  
  22. 	for(int i = 0; i < adj.size(); i++){
  23. 		int a = adj[i];
  24.  
  25. 		if(!vis[a]){
  26.  
  27. 			 children++;
  28. 			 parent[a] = v;
  29.  
  30. 			 dfs(a);
  31.  
  32. 			 low[v] = min(low[v], low[a]);
  33.  
  34. 			 //verifica se é vertice de corte
  35. 			 if(parent[v] == 0 && children > 1){
  36. 			 	x = 1;
  37. 			 	cut[v] = 1;
  38. 			 }
  39.  
  40. 			 //verifica se é vertice de corte
  41. 			 if(parent[v] != 0 && low[a] >= d[v]){
  42. 			 	x = 1;
  43. 			 	cut[v] = 1;
  44. 			 }
  45.  
  46. 			 //verifica se aresta é ponte
  47. 			 if(low[a] > low[v]){
  48. 			// 	cout<<v<<" "<<a<<" |";
  49. 			 }
  50.  
  51. 		}else if(a != parent[v]){
  52. 			low[v] = min(low[v], d[a]);
  53. 		}
  54. 	}
  55. }
  56.  
  57. int main() {
  58.  
  59. 	int n = 0, m = 0, v1 = 0, v2 = 0, c = 0;
  60.  
  61. 	cin>>n>>m;
  62.  
  63. 	while(n!= 0 || m != 0){
  64.  
  65. 		grafo = vector <vector<int>>(n+1);
  66. 		d = low = parent = vector<int>(n+1);
  67. 		cut = vis = vector <bool> (n+1);
  68.  
  69. 		while(m--){
  70. 			cin>>v1>>v2;
  71. 			grafo[v1].push_back(v2);
  72. 			grafo[v2].push_back(v1);
  73. 		}
  74.  
  75. 		raiz = 1;
  76. 		c++;
  77. 		dfs(1);
  78.  
  79. 		cout<<"Teste: "<<c<<endl;
  80. 		if(x==1){
  81. 		for(int i = 0; i< cut.size(); i++){
  82. 			if(cut[i]){
  83. 				cout<<i<<" ";
  84. 			}
  85. 		}
  86.  
  87. 		}else{
  88. 			cout<<"nenhum";
  89. 		}
  90. 		cout<<endl<<endl;
  91.  
  92. 		x = 0;
  93. 		cin>>n>>m;
  94. 	}
  95.  
  96. 	return 0;
  97. }
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
7 8
1 2
2 3
3 1
2 4
4 5
5 6
6 2
2 7
0 0
stdout
copy 
Teste: 1
2
https://ideone.com/ONxq3p
language:
C++14 (gcc 8.3)
created:
6 years 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!