fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n, m;
  5. vector<int>adj[1001];
  6. bool visited[1001];
  7.  
  8. void inp(){
  9. 	cin >> n >> m;
  10. 	for(int i=1; i<=n; i++)adj[i].clear();
  11. 	for(int i=0; i<m; i++){
  12. 		int x, y; cin >> x >> y;
  13. 		adj[x].push_back(y);
  14. 		adj[y].push_back(x);
  15. 	}
  16. 	memset(visited, false, sizeof(visited));
  17. }
  18.  
  19. void dfs(int u){
  20. 	visited[u]=true;
  21. 	for(int v : adj[u]){
  22. 		if(!visited[v]) dfs(v);
  23. 	}
  24. }
  25.  
  26. void dinhtru(){
  27. 	int tplt=0, ans=0;
  28. 	for(int i=1; i<=n; i++){
  29. 		if(!visited[i]){
  30. 			tplt++;
  31. 			dfs(i);
  32. 		}
  33. 	}
  34. 	vector<int> dt;
  35. 	for(int i=1; i<=n; i++){
  36. 		memset(visited, false, sizeof(visited));
  37. 		visited[i]=true;
  38. 		int dem=0;
  39. 		for(int j=1; j<=n; j++){
  40. 			if(!visited[j]){
  41. 				dem++;
  42. 				dfs(j);
  43. 			}
  44. 		}
  45. 		if(dem>tplt){
  46. 			ans++;
  47. 			dt.push_back(i);
  48. 		} 	
  49. 	}
  50.  
  51. 	cout << ans << endl;
  52. 	for(int x : dt){
  53. 		cout << x << " ";
  54. 	}
  55. 	if(ans) cout << endl;
  56. }
  57.  
  58. int main(){
  59. 	int test; cin >> test;
  60. 	while(test--){
  61. 		inp();
  62. 		dinhtru();
  63. 	}
  64.  
  65. 	return 0;
  66. }
Success #stdin #stdout 0.01s 5544KB
comments (?)
stdin
copy 
1
10 6
5 4
5 2
10 2
10 7
5 3
10 1
stdout
copy 
3
2 5 10
https://ideone.com/dnAQ4V
language:
C++ (gcc 8.3)
created:
1 year 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!