fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <vector>
  4. #include <queue>
  5.  
  6. using namespace std;
  7. vector<int>G[1000001];
  8. queue<int>Q;
  9. bool odwiedzony[1000001];
  10. int poprzednik[1000001];
  11. int odl[1000001];
  12. int ta[1000001];
  13. int tb[1000001];
  14. int a,b,n,m,k;
  15. void wczytaj()
  16. {
  17. cin>>n>>m;
  18. for(int i=1;i<=m;i++)
  19. {
  20. cin>>a>>b;
  21. G[a].push_back(b);     
  22. G[b].push_back(a);
  23. ta[i]=a;
  24. tb[i]=b;     
  25. }
  26. }
  27. void BFS(int s)
  28. {
  29. Q.push(s);     
  30. odwiedzony[s]=true;    
  31. while(!Q.empty())
  32. {
  33. k=Q.front();             
  34. Q.pop();             
  35. for(vector<int>::iterator p=G[k].begin();p!=G[k].end();p++)
  36. //int en=G[k].size()
  37. //for(int i=1;i<=en;i++)
  38. {
  39. if(!odwiedzony[*p])
  40. {
  41. odwiedzony[*p]=true;
  42. Q.push(*p);
  43. poprzednik[*p]=k;
  44. odl[*p]=odl[k]+1;                
  45. }                       
  46. }                
  47. }      
  48. }
  49. bool spr()
  50. {
  51. bool b;
  52. b=true;    
  53. for(int i=1;i<=m;i++)
  54. {
  55. if((odl[ta[i]]+odl[tb[i]])%2==0)       
  56. {
  57. b=false;
  58. break;                        
  59. }  
  60. }
  61. return b;    
  62. }
  63. int main()
  64. {
  65. wczytaj();
  66. for(int i=1;i<=n;i++)
  67. if(!odwiedzony[i])
  68.   BFS(i);
  69. if(spr())
  70. cout<<"TAK";
  71. else
  72. cout<<"NIE";
  73. //wypisz();
  74. //system("PAUSE");
  75. return 0;
  76. }
Success #stdin #stdout 0.01s 32572KB
comments (?)
stdin
copy 
3 3
 1 2
 2 3
 3 1
stdout
copy 
NIE
https://ideone.com/qZhnn8
language:
C++ (gcc 8.3)
created:
11 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!