forked from bamsarts/DS-ALGO
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathbipartite graph bug problem.cpp
69 lines (65 loc) · 1.1 KB
/
bipartite graph bug problem.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
using namespace std;
vector<int> adj[20001];
bool visited[20001],col[20001];
bool dfs(int node,int c)
{
visited[node]=1;
col[node]=c;
for(int child:adj[node])
{
if(visited[child]==0)
{
bool res=dfs(child,c^1);
if(res==false)
return false;
}
else if(col[node]==col[child])
return false;
}
return true;
}
void initialise()
{
for(int i=0;i<20001;i++)
visited[i]=false;
}
int main()
{
int t;
cin>>t;
for(int t1=0;t1<t;t1++)
{
int c=0,i,j,nodes,edges,x,y;
cin>>nodes;
cin>>edges;
for(i=1;i<=nodes;i++)
{
adj[i].clear();
}
for(i=0;i<edges;i++)
{
cin>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
initialise();
bool flag=true;
for(i=1;i<=nodes;i++)
{
//cout<<"hi";
if(visited[i]==false)
{
bool res=dfs(i,0);
if(res==false)
flag=false;
}
}
cout<<"Scenario #"<<t1+1<<":"<<endl;
if(flag==false)
cout<<"Suspicious bugs found!";
else
cout<<"No suspicious bugs found!";
cout<<endl;
}
}