Advertisement
Saleh127

UVA 10004

Oct 25th, 2020
73
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[100000];
  6. ll visit[100000],c[10000];
  7. bool dfs(ll ind,ll color)
  8. {
  9. visit[ind]=color;
  10. c[ind]=color;
  11. for(auto i : g[ind])
  12. {
  13. if(visit[i]==0)
  14. {
  15. if(dfs(i,color^1)==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. while(cin>>n>>m && n&&m)
  34. {
  35. for(i=0; i<n; i++)
  36. {
  37. g[i].clear();
  38. visit[i]=0;
  39. }
  40.  
  41. for(i=0; i<m; i++)
  42. {
  43. cin>>k>>l;
  44. g[k].push_back(l);
  45. g[l].push_back(k);
  46. }
  47. if(dfs(0,1)==true) cout<<"BICOLORABLE."<<endl;
  48. else cout<<"NOT BICOLORABLE."<<endl;
  49. }
  50.  
  51.  
  52. return 0;
  53. }
  54.  
Advertisement
RAW Paste Data Copied
Advertisement