SHARE
TWEET

Untitled

a guest Feb 20th, 2019 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. int licznik;
  7. int test;
  8. int n;
  9. int m;
  10. int kolorki = 0;
  11. int kolory[1000100];
  12. vector <int> graf[1000100];
  13. int visited[1000100];
  14.  
  15. void CLEARfunction()
  16. {
  17.     for (int i = 0; i < n+2 ; i++)
  18.     {
  19.         kolory[i] = 0;
  20.         kolorki = 1;
  21.         visited[i] = 0;
  22.         graf[i].clear();
  23.     }
  24. }
  25.  
  26. void DFSfunction(int u)
  27. {
  28.     kolory[u] = kolorki;
  29.     visited[u] = 1;
  30.     kolorki ++;
  31.     for (int i = 0; i < graf[u].size(); i++)
  32.     {
  33.         int v = graf[u][i];
  34.             if(kolory[v] == 0)
  35.             {
  36.                 kolory[v] = kolorki;
  37.             }
  38.  
  39.             if((kolory[u]%2 == 0 && kolory[v]%2 == 0) || (kolory[u]%2 == 1 && kolory[v]%2 == 1))
  40.             {
  41.                 licznik++;
  42.             }
  43.  
  44.         if (visited[v] == 0)
  45.         {
  46.             if((kolory[u]%2 == 0 && kolory[v]%2 == 0) || (kolory[u]%2 == 1 && kolory[v]%2 == 1))
  47.             {
  48.                 licznik++;
  49.             }
  50.             DFSfunction(v);
  51.         }
  52.     }
  53. }
  54.  
  55. void DFS()
  56. {
  57.     cin >> n;
  58.     cin >> m;
  59.     for (int i = 0; i < m; i++)
  60.     {
  61.         int a;
  62.         int b;
  63.         cin >> a;
  64.         cin >> b;
  65.         graf[a].push_back(b);
  66.         graf[b].push_back(a);
  67.     }
  68.  
  69.     DFSfunction(1);
  70. }
  71.  
  72. void CHECKfunction()
  73. {
  74.     /*for(int i = 1 ; i <= n ; i++)
  75.     {
  76.         cout << kolory[i] << " ";
  77.     }
  78.     cout << "\n";*/
  79.     if(licznik > 0)
  80.     {
  81.         cout << "NIE\n";
  82.     }
  83.     else
  84.     {
  85.         cout << "TAK\n";
  86.     }
  87. }
  88.  
  89. int main()
  90. {
  91.     ios_base::sync_with_stdio(0);
  92.     cin.tie(0);
  93.     cout.tie(0);
  94.  
  95.     cin >> test;
  96.     for (int t = 0; t < test; t++)
  97.     {
  98.         DFS();
  99.  
  100.         CHECKfunction();
  101.  
  102.         CLEARfunction();
  103.     }
  104.     return 0;
  105. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top