SPOJSolutions/BUGLIFE.cpp at master · rishijain01/SPOJSolutions · GitHub

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<bits/stdc++.h>

// Shubhank Khare

#include<bits/stdc++.h>
using namespace std;

#define MOD 1000000007

#define VALUEIN
#ifdef VALUEIN
#define valuein(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define valuein(...)
#endif

static auto _ = []()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();

long int graph[2001][2001]={0};
int colour[2001];
using namespace std;
bool is_bip(long int n,long int src)
{
    //int colour[n];
    //for(long int i=0;i<n;i++) colour[i]=-1;
    colour[src]=1;
    queue<long int >q;
    q.push(src);
    while(!q.empty())
    {
        long int u=q.front();
        q.pop();
        if(graph[u][u]==1)
            return false;
        for(long int i=0;i<n;i++)
        {
            if(graph[u][i]&&colour[i]==-1)
            {
                colour[i]=1-colour[u];
                q.push(i);
            }
            else if(graph[u][i]&&colour[u]==colour[i])
                   return false;
        }
    }
    return true;
}
bool check(long int n)
{
    //bool visited[n];
    //memset(visited,false,sizeof(visited));
    for(long i=0;i<n;i++) colour[i]=-1;
    for(long int i=0;i<n;i++)
    {
        if(colour[i]==-1)
           if(!is_bip(n,i))
           {
               return false;
           }
    }
    return true;
}
int main()
{
    long int t;
    cin>>t;
    for(long int tt=1;tt<=t;tt++)
    {
        long int n,m;
        cin>>n>>m;
        memset(graph,0,sizeof(graph));
        while(m--)
        {
            long int i,j;
            cin>>i>>j;
            i--,j--;
            graph[i][j]=1;
            graph[j][i]=1;
        }
        printf("Scenario #%d:\n",tt);
        if(!check(n))
        {
            printf("Suspicious bugs found!\n");
        }
        else
        {
            printf("No suspicious bugs found!\n");
        }
    }
}