fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. class Graph
  8. {
  9. private : 
  10. 	bool flag;
  11. 	bool oddCycle;
  12. 	stack<int> stk;
  13. 	int v, e, head, before, ccnt; //cycle을 이루고 있는 정점의 개수 
  14. 	vector<vector<int> > adj;
  15. 	vector<bool> visited;
  16.  
  17. public:
  18. 	Graph(int _v, int _e) 
  19. 		: v(_v), e(_e), flag(true), oddCycle(false), before(-1)
  20. 	{
  21. 		adj.resize(0);
  22. 		visited.resize(0);
  23. 	}
  24.  
  25. 	void SortList()
  26. 	{
  27. 		for(int i=1; i<=v; i++)
  28. 			sort(adj[i].begin(), adj[i].end());
  29. 	}
  30.  
  31. 	void Init(int _v, int _e)
  32. 	{
  33. 		v=_v; e=_e;
  34. 		head = 0; ccnt=0;
  35. 		adj.resize(v+1);
  36. 		visited.resize(v+1, false);
  37. 	}
  38.  
  39. 	void AddEdge(int u, int v)
  40. 	{
  41. 		adj[u].push_back(v);
  42. 		adj[v].push_back(u);
  43. 	}
  44.  
  45. 	void FindCycle(stack<int> stk)
  46. 	{
  47. 		int head = stk.top();
  48. 		bool flag;
  49. 		ccnt=0;
  50.  
  51. 		stk.pop();
  52.  
  53. 		while(!stk.empty())
  54. 		{			
  55. 			ccnt++;
  56.  
  57. 			if(stk.top()==head)
  58. 			{
  59. 				flag = true;
  60. 				break;
  61. 			}
  62. 			stk.pop();
  63. 		}
  64.  
  65. 		if(!flag) ccnt=0;
  66. 	}
  67.  
  68. 	void DFS(int curr, int before)
  69. 	{
  70. 		if(visited[curr]) return;
  71.  
  72. 		visited[curr]=true;
  73. 		stk.push(curr);
  74.  
  75. 		for(int i=0; i<adj[curr].size(); i++)
  76. 		{
  77. 			int next = adj[curr][i];
  78.  
  79. 			if(next == before) continue;
  80.  
  81. 			if(visited[next])
  82. 			{
  83. 				head = next;
  84. 				stk.push(next);
  85. 				FindCycle(stk);
  86. 				stk.pop();
  87.  
  88. 				if(ccnt%2==1)
  89. 					oddCycle=true;
  90. 			}
  91.  
  92. 			DFS(next, curr);
  93. 		}
  94.  
  95. 		stk.pop();
  96. 		return;
  97. 	}
  98.  
  99. 	void ResetStk()
  100. 	{
  101. 		while(!stk.empty())
  102. 			stk.pop();
  103. 	}	
  104.  
  105. 	bool IsOddCycleExist()
  106. 	{
  107. 		return oddCycle;
  108. 	}
  109. };
  110.  
  111. int main()
  112. {
  113. 	ios::sync_with_stdio(false);
  114. 	cin.tie(NULL);
  115. 	int k, v, e;
  116.  
  117. 	cin>>k;
  118.  
  119. 	while(k--)
  120. 	{
  121. 		Graph g(0, 0);	
  122. 		bool ansFlag=false;
  123.  
  124. 		cin>>v>>e;
  125.  
  126. 		g.Init(v, e);
  127.  
  128. 		for(int i=0; i<e; i++)
  129. 		{
  130. 			int a, b;
  131. 			cin>>a>>b;
  132. 			g.AddEdge(a, b);
  133. 		}
  134.  
  135. 		g.SortList();
  136.  
  137. 		for(int i=1; i<=v; i++)
  138. 		{
  139. 			g.DFS(i, -1);
  140.  
  141. 			g.ResetStk();
  142.  
  143. 			if(g.IsOddCycleExist())	
  144. 			{
  145. 				ansFlag=true;
  146. 				break;
  147. 			}
  148. 		}
  149. 		if(ansFlag)
  150. 			cout<<"NO\n";
  151. 		else
  152. 			cout<<"YES\n";
  153.  
  154. 	}
  155.  
  156. 	return 0;
  157. }
Success #stdin #stdout 0s 4292KB
comments (?)
stdin
copy 
1
4 4
2 1
3 2
4 3
4 1
stdout
copy 
NO
https://ideone.com/kxBUJn
language:
C++14 (gcc 8.3)
created:
3 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!