fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5. 	int n,e,t,u,v,co;
  6. 	scanf("%d",&t);
  7. 	for(int z=1;z<=t;z++){
  8. 		scanf("%d %d",&n,&e);
  9. 		int indeg[n];
  10. 		int col[n];
  11. 		vector<int> gr[n];
  12. 		vector<int> rgr[n];
  13. 		memset(col, 0, sizeof(col));
  14. 		memset(indeg, 0, sizeof(indeg));
  15. 		for(int i=0;i<e;i++){
  16. 			scanf("%d %d",&u,&v);
  17. 			gr[u-1].push_back(v-1);
  18. 			rgr[v-1].push_back(u-1);
  19. 			indeg[v-1]=1;
  20. 		}
  21. 		co=0;
  22. 		for(int i=0;i<n;i++){
  23. 			if(indeg[i]==0){
  24. 				//printf("%d\n",i);
  25. 				indeg[i]=1;
  26. 				col[i]=1;
  27. 				co++;
  28. 				queue<int> q;
  29. 				q.push(i);
  30. 				while(!q.empty()){
  31. 					u=q.front();
  32. 					q.pop();
  33. 					for(int j=0;j<gr[u].size();j++){
  34. 						if(col[gr[u][j]]==0){
  35. 							col[gr[u][j]]=1;
  36. 							q.push(gr[u][j]);
  37. 						}
  38. 					}
  39. 				}
  40. 			}
  41. 		}
  42.  
  43.  
  44. 		for(int i=0;i<n;i++){
  45. 			if(col[i]==0){
  46.  
  47. 				col[i]=1;
  48. 				co++;
  49. 				queue<int> q;
  50. 				q.push(i);
  51. 				while(!q.empty()){
  52. 					u=q.front();
  53. 					q.pop();
  54. 					for(int j=0;j<rgr[u].size();j++){
  55. 						if(col[rgr[u][j]]==0){
  56. 							col[rgr[u][j]]=1;
  57. 							q.push(rgr[u][j]);
  58. 						}
  59. 					}
  60. 				}
  61. 				q.push(i);
  62. 				while(!q.empty()){
  63. 					u=q.front();
  64. 					q.pop();
  65. 					for(int j=0;j<gr[u].size();j++){
  66. 						if(col[gr[u][j]]==0){
  67. 							col[gr[u][j]]=1;
  68. 							q.push(gr[u][j]);
  69. 						}
  70. 					}
  71. 				}
  72.  
  73. 			}
  74. 		}
  75. 		printf("Case %d: %d\n",z,co);
  76. 	}
  77. 	return 0;
  78. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
1
6 6
1 2
2 3
3 1
4 5
5 6
6 4
stdout
copy 
Case 1: 2
https://ideone.com/JDfL7D
language:
C++14 (gcc 8.3)
created:
8 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!