fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define lli int
  3. #define endl "\n"
  4. #define MAX 1000005
  5. using namespace std;
  6.  
  7. vector <lli> visited(MAX, -1);
  8. int counter;
  9.  
  10. void DFS(lli i, vector < vector<lli> > v1)
  11. {
  12. 	visited[i] = counter;
  13. 	for(int j = 0; j<v1[i].size(); j++)
  14. 		if(visited[v1[i][j]] == -1)
  15. 			DFS(v1[i][j], v1);
  16. }
  17.  
  18. int main()
  19. {
  20. 	lli t;
  21. 	cin>>t;
  22. 	ios_base::sync_with_stdio(false);
  23. 	cin.tie(NULL);
  24. 	while(t--)
  25. 	{
  26. 		lli n, k, num1, num2;
  27. 		cin>>n>>k;
  28. 		vector < vector<lli> > v1(n+1);
  29. 		vector <pair <lli, lli> > notequal;
  30. 		string s;
  31. 		for(lli i = 0; i<k; i++)
  32. 		{	
  33. 			cin>>num1>>s>>num2;
  34. 			if(s[0] == '=')
  35. 			{
  36. 				v1[num1].push_back(num2);
  37. 				v1[num2].push_back(num1);
  38. 			}
  39. 			else {
  40. 				notequal.push_back({num1, num2});
  41. 			}
  42. 		}
  43.  
  44. 		for(lli i =0 ;i <=n; i++)
  45. 			visited[i] = -1;
  46. 		counter = 0;
  47. 		for(lli i =1; i<=n; i++)
  48. 		{
  49. 			if(v1[i].size() > 0)
  50. 			{
  51. 				if(visited[i] == -1)
  52. 				{
  53. 					counter++;
  54. 					DFS(i, v1);
  55. 				}
  56. 			}
  57. 		}
  58. 		bool ans = true;
  59. 		for(auto c: notequal)
  60. 			if((visited[c.first] == visited[c.second]) && (visited[c.first] != -1))
  61. 			{
  62. 				ans = false;
  63. 				break;
  64. 			}
  65. 		if(ans)
  66. 			cout<<"YES"<<endl;
  67. 		else
  68. 			cout<<"NO"<<endl;
  69. 	}
  70. }
  71.  
Success #stdin #stdout 0s 7000KB
comments (?)
stdin
copy 
2
2 2
1 = 2
1 != 2
3 2
1 = 2
2 != 3
stdout
copy 
NO
YES
https://ideone.com/ToMs5N
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!