fork(2) download
copy 
  1. /*input
  2. 2
  3. 3 2 2
  4. 1 2
  5. 2 3
  6. 1 2
  7. 2 0
  8. 4 5 2
  9. 1 4
  10. 1 2
  11. 1 3
  12. 4 2
  13. 3 4
  14. 2 1
  15. 3 0
  16. */
  17. #include <bits/stdc++.h>
  18. #define fio ios_base::sync_with_stdio(0);cin.tie(0)	
  19. #define FOR(i, a, b) for(int i = a;i < b; i++)		
  20. #define rev(i, a, b) for(int i = a;i > b; i--)		
  21. #define si(a)   scanf("%d", &a) 					
  22. #define pi(a)   printf("%d\n", a)					
  23. typedef long long ll;								//W
  24. #define pb push_back								//E
  25. #define ff first										//A
  26. #define ss second									//K
  27. #define MOD (ll)1000000007
  28. #define M_PI 3.14159265358979323846
  29. #define N 1000005
  30. #define EPS 1e-12
  31. template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
  32. using namespace std;
  33.  
  34. vector<ll> g[N];
  35. bool f[N]={0};
  36. bool curr[N]={0};
  37. //bool sold[N]={0};
  38.  
  39.  
  40. bool solve(ll a, ll b)
  41. {
  42. 	memset(curr, 0, sizeof(curr));
  43. 	if(f[a])
  44. 		return 0;
  45.  
  46. 	queue<pair<ll, ll> > q;
  47. 	q.push({a, b});
  48. 	f[a]=1;
  49. 	curr[a] = 1;
  50. 	ll v, h;
  51.  
  52. 	while(!q.empty())
  53. 	{
  54.  
  55. 		v = q.front().ff;
  56. 		h = q.front().ss;
  57. 		q.pop();
  58. 		if(h>0)
  59. 		{
  60. 			for(auto w:g[v])
  61. 			{
  62. 				if(!curr[w])
  63. 				{
  64. 					if(f[w])
  65. 						return 0;
  66.  
  67. 					curr[w]=1;
  68. 					f[w]=1;
  69. 					q.push({w, h-1});
  70. 				}
  71.  
  72. 			}
  73. 		}	
  74. 	}
  75. 	return 1;
  76. }
  77.  
  78. int main()
  79. {
  80. 	fio;
  81. 	ll t, n, r, m;
  82. 	cin>>t;
  83.  
  84. 	while(t--)
  85. 	{
  86. 		pair<ll, ll> p;	
  87. 		cin>>n>>r>>m;
  88. 		while(r--)
  89. 		{
  90. 			ll x,y;
  91. 			cin>>x>>y;
  92. 			g[y].pb(x);
  93. 			g[x].pb(y);
  94. 		}
  95.  
  96. 		vector<pair<ll, ll> > as;
  97. 		while(m--)
  98. 		{
  99. 			ll x,y;
  100. 			cin>>x>>y;
  101. 			//sold[x] = 1;
  102. 			p = {x, y};
  103. 			as.pb(p);
  104. 		}
  105.  
  106. 		bool fl;
  107. 		for(auto i:as)
  108. 		{
  109. 			fl = solve(i.ff, i.ss);
  110. 			if(!fl)
  111. 				{cout<<"No\n"; break;}
  112. 		}
  113. 		if(fl)		
  114. 		{
  115. 			for(ll i=1;i<=n;i++)
  116. 			if(!f[i])
  117. 			{
  118. 				fl=0;
  119. 				cout<<"No\n"; 
  120. 				break;
  121. 			}
  122. 		}
  123. 		if(fl) cout<<"Yes\n";
  124.  
  125. 		//clear
  126. 		for(ll i=0;i<=n;i++)
  127. 			g[i].clear();
  128. 		as.clear();
  129. 		memset(f, 0, sizeof(f));
  130. 		//memset(sold, 0, sizeof(sold));
  131. 	}
  132.  
  133. 	return 0;
  134. }
  135.  
Success #stdin #stdout 0s 17144KB
comments (?)
stdin
copy 
2
3 2 2
1 2
2 3
1 2
2 0
4 5 2
1 4
1 2
1 3
4 2
3 4
2 1
3 0
stdout
copy 
No
Yes
https://ideone.com/ljgRhi
language:
C++14 (gcc 8.3)
created:
7 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!