fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. int n,m;
  7.  
  8. int main() {
  9.  
  10. cin>>n>>m;
  11. int flag=0;
  12. vector<vector<int>>arr(m,vector<int>(2));
  13. vector<vector<int>>adj(n+1);
  14.  
  15. for(int i=0;i<m;i++)
  16. {
  17. 	cin>>arr[i][0]>>arr[i][1];
  18. }
  19.  
  20. for(int i=0;i<m;i++)
  21. {
  22. 	adj[arr[i][0]].push_back(arr[i][1]);
  23. 	adj[arr[i][1]].push_back(arr[i][0]);
  24. }
  25.  
  26. vector<int>set(n+1,0);
  27.  
  28. for(int i=1;i<=n;i++)
  29. {
  30. 	vector<int>temp=adj[i];
  31. 	int team1=0,team2=0;
  32.  
  33. 	if(set[i]==0)
  34. 	{
  35. 		for(auto x: temp)
  36. 		{
  37. 			if(set[x]==1)
  38. 			{
  39. 				team1=2; team2=1; break;
  40. 			}
  41.  
  42. 			else if(set[x]==2)
  43. 			{
  44. 				team1=1; team2=2; break;
  45. 			}
  46.  
  47. 			else 
  48. 			{
  49. 			    team1=1; team2=2;
  50. 			}
  51.  
  52. 		}
  53.  
  54.  
  55. 	}
  56.  
  57.  
  58. 	else if(set[i]==1)
  59. 	{
  60. 		team1=1;
  61.  
  62. 		for(auto x: temp)
  63. 		{
  64. 			if(set[x]==1)
  65. 			{
  66. 				flag=1; break;
  67. 			}
  68.  
  69. 		}
  70.  
  71. 		team2=2;
  72.  
  73. 		if(flag)
  74. 	    {
  75. 	        cout<<"IMPOSSIBLE"; break;
  76. 	    }
  77. 	}
  78.  
  79.  
  80.  
  81. 	else if(set[i]==2)
  82. 	{
  83. 		team1=2;
  84.  
  85. 		for(auto x: temp)
  86. 		{
  87. 			if(set[x]==2)
  88. 			{
  89. 				flag=1; break;
  90. 			}
  91. 		}
  92.  
  93. 		team2=1;
  94.  
  95. 		if(flag)
  96. 	    {
  97. 	        cout<<"IMPOSSIBLE"; break;
  98. 	    }
  99.  
  100. 	}
  101.  
  102. 	set[i]=team1;
  103. 	for(auto x:temp)
  104. 	{
  105. 		set[x]=team2;
  106. 	}
  107. }
  108.  
  109. if(!flag) for(int i=1;i<=n;i++)cout<<set[i]<<" ";
  110.  
  111. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5 4
1 2
3 4
4 5
5 3
stdout
copy 
IMPOSSIBLE
https://ideone.com/UHGHkV
language:
C++14 (gcc 8.3)
created:
9 days 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!