forked from spaghetti-source/algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathis_bipartite.cc
More file actions
71 lines (67 loc) · 1.49 KB
/
is_bipartite.cc
File metadata and controls
71 lines (67 loc) · 1.49 KB
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
//
// Bipartite graph recognition
//
// Description:
// A graph is bipartite if there is a 2-partition
// such that there are no edges in the same components.
//
// Algorithm:
// Depth first search.
//
// Verified:
// SPOJ3337
//
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <iterator>
#include <functional>
#include <algorithm>
using namespace std;
struct graph {
int n;
vector<vector<int>> adj;
graph(int n = 0) : n(n), adj(n) { }
void add_edge(int src, int dst) {
n = max(n, max(src, dst)+1);
adj.resize(n);
adj[src].push_back(dst);
adj[dst].push_back(src);
}
};
bool is_bipartite(graph g) {
vector<int> color(g.n, -1);
for (int u = 0; u < g.n; ++u) {
if (color[u] != -1) continue;
color[u] = 0;
for (vector<int> S = {u}; !S.empty(); ) {
int v = S.back(); S.pop_back();
for (auto w: g.adj[v]) {
if (color[w] == color[v]) return false;
if (color[w] == -1) {
color[w] = !color[v];
S.push_back(w);
}
}
}
}
return true;
}
int main() {
int ncase;
scanf("%d", &ncase);
for (int icase = 0; icase < ncase; ++icase) {
printf("Scenario #%d:\n", icase+1);
int n, m;
scanf("%d %d", &n, &m);
graph g(n);
for (int i = 0; i < m; ++i) {
int u, v;
scanf("%d %d", &u, &v);
g.add_edge(u-1, v-1);
}
if (is_bipartite(g)) printf("No suspicious bugs found!\n");
else printf("Suspicious bugs found!\n");
}
}