fork download
copy 
  1. // Online C++ compiler to run C++ program online
  2. #include <iostream>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. bool resolveSuspicion(vector<int>& visitedArr, vector<int>& groupMap, vector<vector<int>>& adjList, int index, int flag) {
  7.     visitedArr[index]=1;
  8.     groupMap[index]=flag;
  9.  
  10.     int num=adjList[index].size();
  11.  
  12.     vector<int> currentNodePoints = adjList[index];
  13.  
  14.     for(int i=0; i<num; i++) {
  15.         int currentNode=currentNodePoints[i];
  16.         if((visitedArr[currentNode]==1 && groupMap[currentNode]==flag) || (visitedArr[currentNode]==0 && !resolveSuspicion(visitedArr, groupMap, adjList, currentNode, flag^1)))  {
  17.             return false;
  18.         }
  19.     }
  20.     return true;
  21. }
  22. int main() {
  23.     // Write C++ code here
  24.     int n;
  25.     cin>>n;
  26.  
  27.     for(int i=0; i<n; i++) {
  28.         int bugs, scenarios;
  29.         cin>>bugs>>scenarios;
  30.         vector<vector<int>> scenarioGraph(scenarios, vector<int>(2));
  31.         vector<vector<int>> adjList(bugs);
  32.         for(int i=0; i<scenarios; i++) {
  33.             cin>>scenarioGraph[i][0];
  34.             cin>>scenarioGraph[i][1];
  35.         }
  36.         for(int i=0; i<scenarios; i++) {
  37.             // bugs indexing starting with 0
  38.             int first=scenarioGraph[i][0]-1;
  39.             int second=scenarioGraph[i][1]-1;
  40.             adjList[first].push_back(second);
  41.             adjList[second].push_back(first);
  42.         }
  43.  
  44.         vector<int> visitedArr(bugs,0);
  45.         vector<int> groupMap(bugs,-1);
  46.  
  47.         int resolveFlag=1;
  48.  
  49.         for(int i=0; i<bugs; i++) {
  50.             if(visitedArr[i]==0) {
  51.                 if(!resolveSuspicion(visitedArr, groupMap, adjList, i, 0)) {
  52.                     resolveFlag=0;
  53.                     break;
  54.                 }
  55.             }
  56.         }
  57.         if(resolveFlag==0) {
  58.             cout<<"Scenario #"<< i+1<<":"<<endl<<"Suspicious bugs found!"<<endl;
  59.         } else {
  60.             cout<<"Scenario #"<< i+1<<":"<<endl<<"No suspicious bugs found!";
  61.         }
  62.     }
  63.     return 0;
  64. }
  65.  
  66.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
2
3 3
1 2
2 3
1 3
4 2
1 2
3 4
stdout
copy 
Scenario #1:
Suspicious bugs found!
Scenario #2:
No suspicious bugs found!
https://ideone.com/8qga1R
language:
C++ (gcc 8.3)
created:
9 hours 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!