fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define fs first
  4. #define sc second
  5. #define pii pair<long long,long long>
  6. #define mii map<string,long long>
  7. using namespace std;
  8. vector < vector < long long > >  d(200005);
  9. long long color[200005];
  10. bool danhdau[200005];
  11. class solution
  12. {
  13. 	public:
  14. 	long long n,m,t;
  15. 	const long long nmax=1e6 + 5;
  16. 	mii mymap;
  17. 	vector < string > data;
  18. 	vector < long long > deg;
  19. 	vector < long long > col;
  20. 	vector < long long > color_avai;
  21.  
  22. 	void init()
  23. 	{
  24. 		for(long long i = 0 ; i < 200000 ; i++) d[i].clear();
  25. 		deg.resize(nmax);
  26. 		for(long long i = 0 ; i < n ; i++) deg[i] = 0;
  27.  
  28. 	}
  29. 	void in()
  30. 	{
  31. 		cin >> m >> n ;
  32. 		t = m;
  33. 		for(long long i = 0 ; i < m ; i++) 
  34. 		{
  35. 			string x;
  36. 			cin >> x;
  37. 			data.pb(x);
  38. 			mymap[x] = i+1;
  39. 		}
  40. 		for(long long i = 0 ; i < n ; i++)
  41. 		{
  42. 			string x;
  43. 			cin >> x;
  44. 			string y;
  45. 			cin >> y;
  46. 			d[mymap[x]].pb(mymap[y]);
  47. 			d[mymap[y]].pb(mymap[x]);
  48. 			deg[mymap[x]]++;
  49. 			deg[mymap[y]]++;
  50. 		}
  51. 		for(long long i = 1 ; i <= m ; i++)
  52. 		{
  53. 			set<long long> colo(d[i].begin(),d[i].end());
  54. 			vector<long long> s1(colo.begin(),colo.end());
  55. 			d[i] = s1;
  56. 			deg[i] = d[i].size();
  57. 		}
  58. 	for(long long i = 0 ; i < n ; i++) color[i] = -1;
  59. 	for(long long i = 0 ; i < n ; i++) danhdau[i] = false;
  60. 	//cout << endl;
  61. 		color_avai.clear();
  62. 	//	for(long long i = 1 ; i <= m; i++) cout << deg[i] << " ";
  63. 	//	cout << endl;
  64.  
  65. 		//for(long long i = 0 ; i < color_avai.size(); i++) cout << color_avai[i] << " ";
  66. 		//cout << endl;
  67. 	}
  68. 	string found()
  69. 	{
  70. 		long long val = LLONG_MIN, id = -1;
  71. 		for(long long i = 1 ; i <= m ; i++)
  72. 		{
  73. 			if (deg[i] > val && danhdau[i] == false) 
  74. 			{
  75. 				val = deg[i];
  76. 				id = i;
  77. 			}
  78. 		}
  79. 		//cout << data[id - 1] << endl;
  80. 		if (id != -1) 
  81. 		{
  82. 			deg[id] = -1;
  83. 		danhdau[id] = true;
  84. 		return data[id - 1];}
  85. 		return "";
  86. 		// for(int i = 0 ; i < d[id].size(); i++)
  87. 		// {
  88. 		// 	deg[d[id][i]]--;
  89. 		// }
  90.  
  91. 	}
  92. 	void solve()
  93. 	{
  94.  
  95. 		while (t--)
  96. 		{
  97. 			//for(long long i = 1 ; i <= m ; i++) cout << deg[i] << " ";
  98. 			//cout << endl;
  99. 			set<long long> colo(color_avai.begin(),color_avai.end());
  100. 			vector<long long> s1(colo.begin(),colo.end());
  101. 			color_avai = s1;
  102. 			string x = found();
  103. 			if (x == "") break;
  104. 			if (color[mymap[x]] == -1)
  105. 			{
  106. 				long long j,cnt = 0;
  107.  
  108. 				for(long long i = 0 ; i < color_avai.size(); i++)
  109. 				if (color_avai[i] == i) cnt++;
  110. 				else break;
  111.  
  112. 				for(j = 0 ; j < color_avai.size(); j++)
  113. 				{
  114. 					bool flag1 = true;
  115. 					for(long long i = 0 ; i < d[mymap[x]].size(); i++)
  116. 					{
  117. 						if (color_avai[j] == color[d[mymap[x]][i]]) flag1 = false;
  118. 					}
  119. 					if (flag1 == true)
  120. 					{
  121. 						color[mymap[x]] = color_avai[j];
  122. 						break;
  123. 					}
  124. 				} 
  125. 				if (j == color_avai.size())
  126. 				{
  127. 					color[mymap[x]] = cnt;
  128. 					color_avai.pb(cnt);
  129. 				}
  130.  
  131.  
  132. 			}
  133. 			else
  134. 			{
  135. 				long long j, cnt = 0;
  136.  
  137. 				for(long long i = 0 ; i < color_avai.size(); i++)
  138. 				if (color_avai[i] == i) cnt++;
  139. 				else break;
  140. 				// cout << "Color available: " << color_avai.size() << endl;
  141. 				// cout << cnt << endl;
  142. 				bool flag = true;
  143. 				for(long long i = 0 ; i < d[mymap[x]].size(); i++)
  144. 				if (color[mymap[x]] == color[d[mymap[x]][i]]) 
  145. 				{
  146. 					flag = false;
  147. 					break;
  148. 				}
  149. 				if (flag == false) {
  150. 				for(j = 0 ; j < color_avai.size(); j++)
  151. 				{
  152. 					bool flag1 = true;
  153. 					for(long long i = 0 ; i < d[mymap[x]].size(); i++)
  154. 					{
  155. 						if (color_avai[j] == color[d[mymap[x]][i]]) flag1 = false;
  156. 					}
  157. 					if (flag1 == true)
  158. 					{
  159. 						color[mymap[x]] = color_avai[j];
  160.  
  161. 						break;
  162. 					}
  163. 				} 
  164. 				if (j == color_avai.size())
  165. 				{
  166. 					color[mymap[x]] = cnt;
  167. 					color_avai.pb(cnt);
  168.  
  169. 				}
  170. 				}
  171.  
  172. 			}
  173.  
  174.  
  175.  
  176. 		}
  177. 	}
  178.  
  179. 	void out()
  180. 	{
  181. 		for(long long i = 1 ; i <= m ; i++) cout << color[i] << " ";
  182.  
  183. 	}
  184. };
  185. int main() {
  186. 	ios::sync_with_stdio(false);
  187. 	cin.tie(0); cout.tie(0);
  188. 	solution *sol = new solution;
  189. 	sol->init();
  190. 	sol->in();
  191. 	sol->solve();
  192. 	sol->out();
  193. 	return 0;
  194. }
Success #stdin #stdout 0.01s 15788KB
comments (?)
stdin
copy 
4 12
A B C D
A B
B A
B C
C B
C A
A C
A D
D A
B D
D B
C D
D C
stdout
copy 
0 1 2 3
https://ideone.com/uDFwyk
language:
C++14 (gcc 8.3)
created:
1 year 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!