Advertisement
Saleh127

CSES 1668

Oct 29th, 2020
100
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  5. vector<ll>g[100005];
  6. ll visit[100005],c[100005];
  7. bool dfs(ll ind,ll color)
  8. {
  9. visit[ind]=1;
  10. c[ind]=color;
  11. for(auto i : g[ind])
  12. {
  13. if(c[i]==0)
  14. {
  15. if(dfs(i,c[ind]^3)==false) return false;
  16. }
  17. else
  18. {
  19. if(c[i]==c[ind]) return false;
  20. }
  21. }
  22. return true;
  23. }
  24.  
  25. int main()
  26. {
  27. ios_base::sync_with_stdio(0);
  28. cin.tie(0);
  29. cout.tie(0);
  30.  
  31. ll n,m,i,j,k,l;
  32.  
  33. cin>>n>>m;
  34.  
  35.  
  36. memset(visit,0,sizeof(visit));
  37. memset(c,0,sizeof(c));
  38.  
  39. for(i=0; i<m; i++)
  40. {
  41. cin>>k>>l;
  42. g[k].push_back(l);
  43. g[l].push_back(k);
  44. }
  45. bool dd=0;
  46. for(i=1;i<=n;i++)
  47. {
  48. if(visit[i]==0)
  49. {
  50. if(dfs(i,1)==0)
  51. {
  52. dd=1;
  53. }
  54. }
  55. }
  56.  
  57. if(dd==1) cout<<"IMPOSSIBLE"<<endl;
  58. else
  59. {
  60. for(i=1;i<=n;i++)
  61. {
  62. cout<<c[i]<<" ";
  63. }
  64. }
  65. return 0;
  66. }
  67.  
Advertisement
RAW Paste Data Copied
Advertisement