fork(1) download
copy 
  1.    #include<iostream>
  2. #include<cstdio>
  3. #include<vector>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<string>
  7. #include<set>
  8. #include<queue>
  9. #include<map>
  10. using namespace std;
  11. #define max 100001
  12. vector<long long>v[max];
  13. void bfs();
  14. long long check=0;
  15. set<long long>v1;
  16. void DFS();
  17. void DFS_VISIT(long long u);
  18. string color[max];
  19. vector<long long>top_sort;
  20. queue<long long>q;
  21. int main()
  22. {
  23. 	long long k=0,i;
  24. 	long long n,m;
  25. 	map< long long,long long > city;
  26. 	long long  ind=0;
  27. 	while(cin>>n>>m)
  28. 	{
  29.  
  30.  
  31. 		if(n<0&&m<0)
  32. 		{
  33. 			break;
  34. 		}
  35.  
  36. 		if(city[n]==0)
  37. 		{
  38. 			city[n]=++ind;
  39.  
  40. 		}
  41.  
  42. 		if(city[m]==0)
  43. 		{
  44. 			city[m]=++ind;
  45.  
  46.  
  47. 		}
  48. 		if(n>0&&m>0)
  49. 		{
  50. 			v[city[n]].push_back(city[m]);
  51. 			v1.insert(city[n]);
  52. 			v1.insert(city[m]);
  53. 		}
  54. 		if(n==0&&m==0)
  55. 		{
  56.  
  57. 			check=0;
  58. 			if(v1.size()>0)
  59. 			{
  60. 				DFS();
  61. 				bfs();
  62. 			}
  63. 			if(v1.size()==0)
  64. 				printf("Case %lld is a tree.\n",++k);
  65. 			else if(check==0)
  66. 				printf("Case %lld is a tree.\n",++k);
  67. 			else
  68. 				printf("Case %lld is not a tree.\n",++k);
  69.  
  70. 			top_sort.clear();
  71. 			set<long long>::iterator it;
  72. 			for (it=v1.begin();it!=v1.end();it++)
  73. 			{
  74. 				v[*it].clear();
  75. 			}
  76. 			city.clear();
  77. 			while(!q.empty())
  78. 				q.pop();
  79. 			v1.clear();
  80. 			ind=0;
  81. 		}
  82. 	}
  83. }
  84. void DFS()
  85. {
  86.  
  87. 	set<long long>::iterator it;
  88.  
  89. 	for (it=v1.begin();it!=v1.end();it++)
  90. 	{
  91. 		color[*it] = "WHITE";
  92. 	}
  93. 	set<long long>::iterator it1;
  94. 	for (it1=v1.begin();it1!=v1.end();it1++)
  95. 	{
  96. 		if (color[*it1] == "WHITE")
  97. 		{
  98. 			DFS_VISIT(*it1);
  99. 		}
  100. 	}
  101. }
  102. void DFS_VISIT(long long  u)
  103. {
  104. 	long long  i;
  105. 	color[u] = "GRAY";
  106. 	for (i = 0; i<v[u].size(); i++)
  107. 	{
  108. 		if (color[v[u][i]] == "WHITE")
  109. 		{
  110. 			DFS_VISIT(v[u][i]);
  111. 		}
  112. 	}
  113. 	color[u] = "BLACK";
  114. 	top_sort.push_back(u);
  115. }
  116. void bfs()
  117. {
  118. 	int taken[max];
  119. 	memset(taken,-1,sizeof(taken));
  120. 	long long i,u2,v2,j;
  121. 	for(i=top_sort.size()-1;i>=0;i--)
  122. 	{
  123. 		if(taken[top_sort[i]]!=1)
  124. 		{
  125. 			taken[top_sort[i]]=1;
  126. 			q.push(top_sort[i]);
  127. 			while(!q.empty())
  128. 			{
  129. 				u2=q.front();
  130. 				q.pop();
  131. 				for(j=0;j<v[u2].size();j++)
  132. 				{
  133. 					v2=v[u2][j];
  134. 					if(taken[v2]==1)
  135. 					{
  136. 						check=1;
  137. 					}
  138. 					if(taken[v2]==-1)
  139. 					{
  140. 						taken[v2]=1;
  141. 						q.push(v2);
  142. 					}
  143. 				}
  144. 			}
  145. 		}
  146. 	}
  147. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
1 2 2 3 3 4
0 0
-1 -1
stdout
copy 
Case 1 is a tree.
https://ideone.com/7bNsHQ
language:
C++ (gcc 8.3)
created:
9 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!