Advertisement
Josif_tepe

Untitled

May 15th, 2022
687
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.04 KB | None
  1. #include <iostream>
  2. #include <queue>
  3. #include <cstring>
  4. using namespace std;
  5. typedef long long ll;
  6. int n, m;
  7. vector<int> graph[1005];
  8. int color[1005];
  9. bool visited[1005];
  10. bool dfs(int node) {
  11.     for(int i = 0; i < graph[node].size(); i++) {
  12.         int sosed = graph[node][i];
  13.         if(!visited[sosed]) {
  14.             visited[sosed] = true;
  15.             color[sosed] = 1 - color[node];
  16.             if(!dfs(sosed)) {
  17.                 return false;
  18.             }
  19.         }
  20.         else if(color[sosed] == color[node]) {
  21.             return false;
  22.         }
  23.     }
  24.     return true;
  25. }
  26. int main() {
  27.     ios_base::sync_with_stdio(false);
  28.     cin >> n >> m;
  29.     for(int i = 0; i < m; i++) {
  30.         int a, b;
  31.         cin >> a >> b;
  32.         graph[a].push_back(b);
  33.         graph[b].push_back(a);
  34.     }
  35.     for(int i = 0; i <= n; i++) {
  36.         color[i] = -1;
  37.         visited[i] = false;
  38.     }
  39.     color[0] = 1;
  40.    
  41.     if(dfs(0)) {
  42.         cout << "YES" << endl;
  43.     }
  44.     else {
  45.         cout << "NO" << endl;
  46.     }
  47.     return 0;
  48. }
  49.  
Advertisement
RAW Paste Data Copied
Advertisement