fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. vector<int> e[10010];
  8.  
  9. int cnt = 0;
  10. int low[10010];
  11. int pre[10010];
  12.  
  13. vector<int> sep;
  14.  
  15. void dfs(int u, int par) {
  16. 	int child = 0;
  17. 	pre[u] = ++cnt;
  18. 	low[u] = cnt;
  19. 	int flag = 0;
  20. 	for(auto &v : e[u]) {
  21. 		if(v == par) continue;
  22. 		if(pre[v] == 0) {
  23. 			child++;
  24. 			dfs(v, u);
  25. 			if(low[u] > low[v]) low[u] = low[v];
  26. 			if(pre[u] <= low[v]) flag = 1;
  27. 		}
  28. 		else {
  29. 			if(pre[v] < low[u]) low[u] = pre[v];
  30. 		}
  31. 	}
  32.  
  33. 	if(par != -1 && flag) sep.push_back(u);
  34. 	if(par == -1 && child >= 2) sep.push_back(u);
  35. }
  36.  
  37. int main() {
  38. 	int n, m;
  39. 	scanf("%d %d", &n, &m);
  40. 	for(int i = 0; i < m; i++) {
  41. 		int x, y;
  42. 		scanf("%d %d", &x, &y);
  43. 		e[x].push_back(y);
  44. 		e[y].push_back(x);
  45. 	}
  46. 	for(int i = 1; i <= n; i++) {
  47. 		if(pre[i]) continue;
  48. 		dfs(i, -1);
  49. 	}
  50. 	printf("%d\n", sep.size());
  51. 	sort(sep.begin(), sep.end());
  52. 	for(auto &v : sep) printf("%d ", v);
  53. 	return 0;
  54. }
Success #stdin #stdout 0s 4560KB
comments (?)
stdin
copy 
7 7
1 4
4 5
5 1
1 6
6 7
2 7
7 3
stdout
copy 
3
1 6 7
https://ideone.com/6LNUrj
language:
C++14 (gcc 8.3)
created:
4 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!