Niloy007

BUGLIFE - A Bug’s Life

Apr 11th, 2020
294
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 max 100000
  4. vector<int> graph[max];
  5. vector<int> visited;
  6. int color[max];
  7.  
  8. void dfs(int n) {
  9.     visited[n] = true;
  10.  
  11.     for (int i : graph[n]) {
  12.         if (color[n] == 0) {
  13.             color[i] = 1;
  14.         } else if (color[n] == 1) {
  15.             color[i] = 0;
  16.         }
  17.  
  18.         if (!visited[i]) {
  19.             dfs(i);
  20.         }
  21.     }
  22. }
  23.  
  24. int main() {
  25.     int t, v, e, count(1);
  26.     int a, b;
  27.     cin >> t;
  28.     while (t--) {
  29.         cin >> v >> e;
  30.         visited.assign(v + 3, false);
  31.         bool bicolorable = true;
  32.         memset(color, 0, sizeof(color));
  33.  
  34.         for(int i = 0; i < v + 3; i++) {
  35.             graph[i].clear();
  36.         }
  37.  
  38.         for (int i = 0; i < e; i++) {
  39.             cin >> a >> b;
  40.             graph[a].push_back(b);
  41.             graph[b].push_back(a);
  42.         }
  43.  
  44.         dfs(a);
  45.  
  46.         int c;
  47.         for (int i = 0; i < v + 3; i++) {
  48.             if (graph[i].size() > 0) {
  49.                 c = color[i];
  50.                 for (int j = 0; j < graph[i].size(); j++) {
  51.                     if (c == graph[i][j]) {
  52.                         bicolorable = false;
  53.                         break;
  54.                     }
  55.                 }
  56.             }
  57.  
  58.             if (!bicolorable) {
  59.                 break;
  60.             }
  61.         }
  62.  
  63.         printf("Scenario #%d:\n",count++);
  64.         if(bicolorable) printf("No suspicious bugs found!\n");
  65.         else printf("Suspicious bugs found!\n");
  66.     }
  67. }
RAW Paste Data