Bài toán
Kiểm tra một đồ thị vô hướng có phải là hai phía.
Độ phức tạp
O(n+m)
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
vector<int> a[12309];
bool Invalid = false;
bool Visited[12309];
int Color[12309];
void visit(int u) {
Visited[u] = true;
for (int i = 0; i < a[u].size(); i++) {
int v = a[u][i];
if (!Visited[v]) {
Color[v] = 3 - Color[u];
visit(v);
}
else {
if (Color[v] == Color[u])
Invalid = true;
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int p, q;
cin >> p >> q;
a[p].push_back(q);
a[q].push_back(p);
}
for (int i = 1; i <= n; i++) {
if (!Visited[i]) {
Color[i] = 1;
visit(i);
}
}
if (Invalid)
cout << "Invalid" << endl;
else {
for (int i = 1; i <= n; i++) cout << Color[i] << " ";
cout << endl;
}
}
Nhận xét