fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define gc getchar_unlocked
  4. #define fo(i,n) for(i=0;i<n;i++)
  5. #define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
  6. #define ll long long
  7. #define si(x)	scanf("%d",&x)
  8. #define sl(x)	scanf("%lld",&x)
  9. #define ss(s)	scanf("%s",s)
  10. #define pi(x)	printf("%d\n",x)
  11. #define pl(x)	printf("%lld\n",x)
  12. #define ps(s)	printf("%s\n",s)
  13. #define pb push_back
  14. #define mp make_pair
  15. #define F first
  16. #define S second
  17. #define all(x) x.begin(), x.end()
  18. #define clr(x) memset(x, 0, sizeof(x))
  19. #define sortall(x) sort(all(x))
  20. #define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
  21. #define PI 3.1415926535897932384626
  22. typedef pair<int, int>	pii;
  23. typedef pair<ll, ll>	pl;
  24. typedef vector<int>		vi;
  25. typedef vector<ll>		vl;
  26. typedef vector<pii>		vpii;
  27. typedef vector<pl>		vpl;
  28. typedef vector<vi>		vvi;
  29. typedef vector<vl>		vvl;
  30. int mpow(int base, int exp); 
  31. void ipgraph(int m);
  32. void dfs(int u, int par);
  33. const ll mod = 1000000007*1LL*1000000007;
  34. const int N = 3e5 + 3, M = N;
  35. //=======================
  36.  
  37. set<int> g[N];
  38. int sz[N], par[N];
  39. int rep(int x){
  40. 	if(x == par[x]) return x;
  41. 	return par[x] = rep(par[x]);
  42. }
  43. void unite(int x, int y){
  44. 	x = rep(x);	
  45. 	y = rep(y);	
  46. 	if(x==y)return;
  47. 	if(sz[x]<sz[y]);
  48. 	else swap(x, y);
  49. 	par[x] = y;
  50. 	if(sz[x] == sz[y])
  51. 		sz[y]++;
  52. }
  53.  
  54. ll h[N], val[N];
  55. ll r(){
  56. 	return rand()*32000+rand();	
  57. }
  58. map<int,int> taken;
  59. set<ll> allvals;
  60. map<ll, vi> com;
  61. int ass[N], T;
  62. void go(int u){
  63.  
  64. 	int cur = ass[u];
  65. 	for(int v: g[u]){
  66. 		if(ass[v]){
  67. 			if(abs(ass[v]-ass[u])>1){
  68. 				cout <<"NO\n";
  69. 				exit(0);
  70. 			}
  71. 		}
  72. 		else{
  73. 			if(!taken[cur+1])
  74. 			ass[v] = cur+1;
  75. 			else if(!taken[cur-1])
  76. 			ass[v] = cur-1;
  77. 			else{
  78. 				cout <<"NO\n";
  79. 				exit(0);
  80. 			}
  81. 			T = max(T, ass[v]+2);
  82. 			taken[ass[v]] = 1;
  83. 			go(v);
  84. 		}
  85. 	}
  86. }
  87. int main()
  88. {
  89. 	ios_base::sync_with_stdio(false);
  90. 	cin.tie(NULL);
  91. 	int i,n,k,j, u, v, x, y, a, b, c, m;
  92. 	cin >> n >> m;
  93. 	srand(1234);
  94. 	Fo(i, 1, n+1) h[i] = (r()*r()+r())%mod;
  95. 	Fo(i, 1, n+1){
  96. 		par[i] = i;
  97. 		sz[i] = 0;
  98. 	}
  99. 	fo(i, m) {
  100. 		cin >> u >> v;
  101. 		g[u].insert(v);
  102. 		g[v].insert(u);
  103. 	}
  104. 	Fo(i, 1, n+1){
  105. 		val[i] = h[i];
  106. 		for(int x: g[i]){
  107. 			val[i] = (val[i] + h[x])%mod;
  108. 		}
  109. 		allvals.insert(val[i]);
  110. 		com[val[i]].pb(i);
  111. 	}
  112. 	for(ll c: allvals){
  113. 		int x = com[c].size();
  114. 		if(x>1){
  115. 			u = com[c][0];
  116. 			for(int v: com[c])
  117. 				unite(u, v);
  118. 		}
  119. 	}
  120. 	Fo(i, 1, n+1){
  121. 		set<int> allnew; allnew.clear();
  122. 		for(int v: g[i]){
  123. 			allnew.insert(rep(v));
  124. 		}
  125. 		g[i].clear();
  126. 		for(int v: allnew) {
  127. 			if(v != i)
  128. 				g[i].insert(v);
  129. 		}
  130. 		int nsz = g[i].size();
  131. 		if(nsz > 2 and i == rep(i)){
  132. 			cout <<"NO\n";
  133. 			return 0;
  134. 		}
  135. 	}
  136. 	T = n+2; //take it bigger enough to avoid negative values
  137. 	Fo(i, 1, n+1){
  138. 		u = rep(i);
  139. 		if(u != i) continue;
  140. 		if(!ass[i]) ass[i] = T,taken[T] = 1, go(i);
  141. 	}
  142. 	cout<<"YES\n";
  143. 	Fo(i, 1, n+1){
  144. 		cout << ass[rep(i)] << " ";
  145. 	}
  146. 	return 0;
  147. } 
  148.  
  149.  
Success #stdin #stdout 0s 37504KB
comments (?)
stdin
copy 
4 4
1 2
1 3
1 4
3 4
stdout
copy 
YES
6 7 5 5
https://ideone.com/cFWGY4
my template :)
language:
C++14 (gcc 8.3)
created:
6 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!