fork download
copy 
  1. #include <iostream>
  2. #include <map>
  3. using namespace std;
  4.  
  5. map<int,map<int ,int> > Map;
  6. int visited[100001];
  7. int team[100001];
  8. bool isPossible=true;
  9.  
  10. void dfs(int i,int t)
  11. {
  12. 	for(auto it=Map[i].begin();it!=Map[i].end();it++)
  13. 	{
  14. 		if(i != t)
  15. 		{
  16. 			if(visited[it->first] == 0)
  17. 			{
  18. 				team[it->first] = !team[i];
  19. 				visited[it->first]=1;
  20. 				dfs(it->first,i);
  21. 			}
  22. 			else
  23. 			{
  24. 				if(team[it->first] == team[i])
  25. 				{
  26. 					isPossible = false;
  27. 				}
  28. 			}
  29. 		}
  30. 	}
  31. }
  32.  
  33.  
  34. int main() {
  35.  
  36. 	int n,m;
  37. 	cin>>n>>m;
  38.  
  39. 	for(int i=0;i<m;i++)
  40. 	{
  41. 		int x,y;
  42. 		cin>>x>>y;
  43. 		Map[x-1][y-1]=1;
  44. 		Map[y-1][x-1]=1;
  45. 	}
  46.  
  47. 	for(int i=0;i<n;i++)
  48. 	{
  49. 		visited[i]=0;
  50. 		team[i]=0;
  51. 	}
  52.  
  53. 	for(int i=0;i<n;i++)
  54. 	{
  55. 		if(visited[i] == 0)
  56. 		{
  57. 			visited[i]=1;
  58. 			dfs(i,-1);
  59. 		}
  60. 	}
  61.  
  62. 	if(isPossible == true)
  63. 	{
  64. 		for(int i=0;i<n;i++)
  65. 		{
  66. 			cout<<team[i]+1<<" ";
  67. 		}
  68. 		cout<<endl;
  69. 	}
  70. 	else
  71. 	{
  72. 		cout<<"IMPOSSIBLE"<<endl;
  73. 	}
  74.  
  75. 	return 0;
  76. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
5 3
1 2
1 3
4 5
stdout
copy 
1 2 2 1 2
https://ideone.com/2r0DP1
language:
C++14 (gcc 8.3)
created:
6 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!