Spoj/BUGLIFE.cpp at master · SharmaManish/Spoj · 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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<iostream>
#include<stdio.h>
#include<queue>

using namespace std;

int main()
{
    int t,count=1;

    scanf("%d",&t);

    while(t--)
    {
              int n,m;

              scanf("%d%d",&n,&m);

              int a[n][n];int start;

              bool flag=true,flag2=true;

              int dist[n];

              for(int i=0;i<n;i++)
              dist[i]=0;

              for(int i=0;i<n;i++)
              for(int j=0;j<n;j++)
              {
                      a[i][j]=0;
              }

              int b,c;

              for(int i=0;i<m;i++)
              {
                      scanf("%d%d",&b,&c);

                      if(flag)
                      {
                              start=b-1;
                              flag=false;
                      }

                      a[b-1][c-1]=1;
                      a[c-1][b-1]=1;
              }

              queue<int> q;

              q.push(start);

              dist[start]=-1;

              while(!q.empty())
              {
                               int x=q.front();

                               q.pop();

                               for(int i=0;i<n;i++)
                               {
                                       if(a[x][i])
                                       {
                                                  if(dist[i]==dist[x])
                                                  {
                                                                      flag2=false;
                                                                      break;
                                                  }

                                                  else if(dist[i]==0)
                                                  {
                                                      if(dist[x]==-1)
                                                      {
                                                                     dist[i]=-2;
                                                                     q.push(i);
                                                      }

                                                      else
                                                      {
                                                          dist[i]=-1;
                                                          q.push(i);
                                                      }

                                                  }

                                       }
                               }

                               if(flag2==false)
                               break;


                               if(q.empty())
                               {
                                            for(int j=0;j<n;j++)
                                            {
                                                    if(dist[j]==0)
                                                    {
                                                                  q.push(j);
                                                                  dist[j]=-1;
                                                                  break;
                                                    }

                                            }

                               }

              }

              if(!flag2)
              printf("Scenario #%d:\nSuspicious bugs found!\n",count);

              else
              printf("Scenario #%d:\nNo suspicious bugs found!\n",count);

              count++;

    }

    system ("pause");

    return 0;

}