fork(1) download
copy 
  1. //feasible relation category dfs difficulty easy
  2. #include<bits/stdc++.h>
  3. #define ull unsigned long long
  4. #define pb push_back
  5. #define mp make_pair
  6. using namespace std;
  7. typedef pair<int,int> pii;
  8. typedef vector<int> vi;
  9. class union_find
  10. {
  11. 	public:
  12. 	vector <int> parent,size;
  13. 	union_find(int n)
  14. 	{
  15. 		parent=vector<int>(n);
  16. 		size=vector<int>(n,1);
  17. 		for(int i=0;i<n;i++)
  18. 		{
  19. 			parent[i]=i;
  20. 		}
  21. 	}
  22. 	//find operation using path compression heuristic
  23. 	//i.e. when root() is called for 'a' make the found root parent of a so we dont have
  24. 	//to traverse up all again in order to find root of 'a'
  25. 	int root(int a)
  26. 	{
  27. 		return parent[a]==a?a:parent[a]=root(parent[a]);
  28. 	}
  29. 	void unionset(int a,int b)
  30. 	{
  31. 		int aroot=root(a);
  32. 		int broot=root(b);
  33. 		if(size[aroot]<size[broot])
  34. 		{
  35. 			parent[aroot]=broot;
  36. 			size[broot]+=size[aroot];
  37. 		}
  38. 		else
  39. 		{
  40. 			parent[broot]=aroot;
  41. 			size[aroot]+=size[broot];
  42. 		}
  43. 	}
  44. };
  45. int main()
  46. {
  47. 	ios::sync_with_stdio(false);
  48. 	//cin.tie(NULL);
  49. 	int test;
  50. 	cin>>test;
  51. 	while(test--)
  52. 	{
  53. 		int n,k;
  54. 		cin>>n>>k;
  55. 		union_find uf(n);
  56. 		cin.ignore();
  57. 		vector<pii > qu;
  58. 		string ans="YES";
  59. 		//cout<<"Yaha\n";
  60. 		while(k--)
  61. 		{
  62. 			string s;
  63. 			getline(cin,s);
  64. 			istringstream iss(s);
  65. 			int a,b;
  66. 			string sa;
  67. 			iss>>a;
  68. 			iss>>sa;
  69. 			iss>>b;
  70. 			a--;
  71. 			b--;
  72. 			//cout<<"Yahaloopme\n";
  73. 			if(sa=="!=")
  74. 			{
  75. 				if(uf.root(a)==uf.root(b))
  76. 				{
  77. 					ans="NO";
  78. 					break;
  79. 				}
  80. 				else
  81. 					qu.pb(mp(a,b));
  82. 			}	
  83. 			else
  84. 				uf.unionset(a,b);
  85. 		}
  86. 		//cout<<"fir";
  87. 		for(int i=0;i<qu.size()&&ans=="YES";i++)
  88. 		{
  89.  
  90. 			if(uf.root(qu[i].first)==uf.root(qu[i].second))
  91. 				{ans="NO"; break;}
  92.  
  93. 		}
  94. 		cout<<ans<<endl;
  95. 	}
  96.  
  97. }
Runtime error #stdin #stdout #stderr 0s 16072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/tznBOM
language:
C++ (gcc 8.3)
created:
6 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!