fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4.  
  5. vector<int> ar[100001];
  6. bool vis[100001];
  7. int col[100001];
  8.  
  9. bool dfs(int node,int c)
  10. {
  11. 	vis[node]=1;
  12. 	col[node]=c;
  13. 	for(int child:ar[node])
  14. 	{
  15. 		if(!vis[child])
  16. 		{
  17. 		 	if(!dfs(child,c ^ 1))
  18. 		 	{
  19. 		 		return false;
  20. 			 }
  21. 		}
  22. 		else if(col[node] == col[child])
  23. 			return false;
  24. 	}
  25. 	return true;
  26. }
  27. int main()
  28. {
  29. 	int n,m,a,b;
  30. 	cin>>n>>m;
  31. 	for(int i=1;i<=m;i++)
  32. 	{
  33. 		cin>>a>>b,ar[a].push_back(b),ar[b].push_back(a);
  34. 	}
  35. 	bool flag=true;
  36. 	for(int i=1;i<=n;i++)
  37. 	{
  38. 		if(vis[i]==false)
  39. 		{
  40. 			if(!dfs(i,1))
  41. 			{
  42. 				flag=false;
  43. 				cout<<"IMPOSSIBLE"<<endl;
  44. 				return 0;
  45. 			}
  46. 		}
  47. 	}
  48. 	if(flag)
  49. 	{
  50. 		for(int i=1;i<=n;i++)
  51. 		{
  52. 			if(col[i]==0)
  53. 				cout<<2<<" ";
  54. 			else
  55. 				cout<<col[i]<<" ";
  56. 		}	
  57. 	}
  58. }
Success #stdin #stdout 0.01s 6132KB
comments (?)
stdin
copy 
5 3
1 2
1 3
4 5
stdout
copy 
1 2 2 1 2
https://ideone.com/us1NMO
language:
C++ (gcc 8.3)
created:
2 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!