A18503. 染色
填空题
困难
知识点
题目描述
染色
题目描述
小杨同学有一张包含 个结点的无向图G， G中的结点依次以 1,2,,,,n 编号。
小杨同学发现G中每个结点的度数都是2。显然G中恰好有n条边。
小杨同学想为G中的结点染色，使得任意一条边两端的结点都有不同的颜色。
小杨同学想知道最少需要多少种颜色才能在满足条件的前提下为G染色。
输入格式
本题包含多组数据。
第一行，一个正整数 t ，表示数据组数。
对于每组数据：
第一行，一个正整数 n，表示无向图 中的结点数。
接下来 n 行，每行两个正整数 ui, vi，表示一条连接结点 ui 与 vi 的无向边，整数之间以空格分隔。
保证G中没有重边与自环。
输出格式
对于每组数据：输出一行，一个整数，表示在满足条件的前提下为 染色需要的最少颜色数。
输入样例
4
6
1 6
2 1
3 2
4 3
5 4
6 5
6
1 3
3 5
5 1
2 4
4 6
6 2
3
1 2
2 3
3 1
5
1 4
2 5
3 1
4 2
5 3输出样例
2
3
3
3参考答案
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int a[100010], b[100010], cnt[100010];
void solve() {
cin >> n;
for (int i = 1; i <= n; i++)
a[i] = b[i] = cnt[i] = 0;
for (int i = 1; i <= n; i++) {
int u, v;
cin >> u >> v;
b[u] = a[u];
a[u] = v;
b[v] = a[v];
a[v] = u;
}
bool flag = false;
for (int i = 1; i <= n; i++) {
if (cnt[i])
continue;
int u = i, last = a[u];
int v = a[u] + b[u] - last;
while (!cnt[v]) {
cnt[v] = cnt[u] + 1;
last = u;
u = v;
v = a[u] + b[u] - last;
}
if (cnt[i] % 2 != 0)
flag = true;
}
if (flag)
cout << 3 << endl;
else
cout << 2 << endl;
}
int main() {
int t;
cin >> t;
while (t--)
solve();
return 0;
}
上一题
下一题