1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 200005;
5
6vector<int> adj[MAXN]; // 邻接表
7int color[MAXN];       // -1=未着色, 0=颜色A, 1=颜色B
8int n, m;
9
10bool bfs(int start) {
11    queue<int> q;
12    color[start] = 0; // 起始顶点染为颜色0
13    q.push(start);
14
15    while (!q.empty()) {
16        int u = q.front();
17        q.pop();
18
19        for (int v : adj[u]) {
20            if (color[v] == -1) {
21                // 未着色，染为u的反色
22                color[v] = 1 - color[u];
23                q.push(v);
24            } else if (color[v] == color[u]) {
25                // 颜色冲突，不是二分图
26                return false;
27            }
28        }
29    }
30    return true;
31}
32
33int main() {
34    ios::sync_with_stdio(false);
35    cin.tie(nullptr);
36
37    cin >> n >> m;
38    memset(color, -1, sizeof(color));
39
40    for (int i = 0; i < m; i++) {
41        int u, v;
42        cin >> u >> v;
43        adj[u].push_back(v);
44        adj[v].push_back(u); // 无向图
45    }
46
47    bool isBipartite = true;
48    for (int i = 1; i <= n; i++) {
49        if (color[i] == -1) {
50            // 新的连通分量
51            if (!bfs(i)) {
52                isBipartite = false;
53                break;
54            }
55        }
56    }
57
58    if (isBipartite)
59        cout << "YES" << endl;
60    else
61        cout << "NO" << endl;
62
63    return 0;
64}

1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 200005;
5
6vector<int> adj[MAXN];
7int color[MAXN]; // -1=未着色, 0/1=两种颜色
8int n, m;
9
10bool dfs(int u, int c) {
11    color[u] = c;
12
13    for (int v : adj[u]) {
14        if (color[v] == -1) {
15            // 未着色，尝试染反色
16            if (!dfs(v, 1 - c)) return false;
17        } else if (color[v] == c) {
18            // 同色冲突
19            return false;
20        }
21    }
22    return true;
23}
24
25int main() {
26    ios::sync_with_stdio(false);
27    cin.tie(nullptr);
28
29    cin >> n >> m;
30    memset(color, -1, sizeof(color));
31
32    for (int i = 0; i < m; i++) {
33        int u, v;
34        cin >> u >> v;
35        adj[u].push_back(v);
36        adj[v].push_back(u);
37    }
38
39    bool isBipartite = true;
40    for (int i = 1; i <= n; i++) {
41        if (color[i] == -1) {
42            if (!dfs(i, 0)) {
43                isBipartite = false;
44                break;
45            }
46        }
47    }
48
49    cout << (isBipartite ? "YES" : "NO") << endl;
50
51    return 0;
52}

1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 200005;
5
6vector<int> adj[MAXN];
7int color[MAXN];
8int n, m;
9
10bool bfs(int start) {
11    queue<int> q;
12    color[start] = 0;
13    q.push(start);
14
15    while (!q.empty()) {
16        int u = q.front(); q.pop();
17        for (int v : adj[u]) {
18            if (color[v] == -1) {
19                color[v] = 1 - color[u];
20                q.push(v);
21            } else if (color[v] == color[u]) {
22                return false;
23            }
24        }
25    }
26    return true;
27}
28
29int main() {
30    ios::sync_with_stdio(false);
31    cin.tie(nullptr);
32
33    cin >> n >> m;
34    memset(color, -1, sizeof(color));
35
36    for (int i = 0; i < m; i++) {
37        int u, v;
38        cin >> u >> v;
39        adj[u].push_back(v);
40        adj[v].push_back(u);
41    }
42
43    bool ok = true;
44    for (int i = 1; i <= n; i++) {
45        if (color[i] == -1 && !bfs(i)) {
46            ok = false;
47            break;
48        }
49    }
50
51    if (!ok) {
52        cout << "NOT BIPARTITE" << endl;
53        return 0;
54    }
55
56    // 输出两个集合
57    vector<int> setA, setB;
58    for (int i = 1; i <= n; i++) {
59        if (color[i] == 0) setA.push_back(i);
60        else setB.push_back(i);
61    }
62
63    cout << "Set A (" << setA.size() << "): ";
64    for (int v : setA) cout << v << " ";
65    cout << endl;
66
67    cout << "Set B (" << setB.size() << "): ";
68    for (int v : setB) cout << v << " ";
69    cout << endl;
70
71    return 0;
72}