牛客——紫魔法师（并查集）
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
题目描述
“サーヴァント、キャスター、Medea。”--紫魔法师
给出一棵仙人掌(每条边最多被包含于一个环，无自环，无重边，保证连通)，要求用最少的颜色对其顶点染色，满足每条边两个端点的颜色不同，输出最小颜色数即可
输入描述:
第一行包括两个整数n,m，表示顶点数和边数 n <= 100000, m <= 200000 接下来m行每行两个整数u,v，表示u,v之间有一条无向边，保证数据合法
输出描述:
一行一个整数表示最小颜色数
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int f[maxn*2];
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
void join(int x,int y){
f[find(x)]=find(y);
}
int main(){
int n,m;
cin>>n>>m;
int ans=2;
for(int i=0;i<=n*2;i++)f[i]=i;
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
if(find(u)==find(v)){
ans=3;
}
join(u,v+n);
join(u+n,v);
}
cout<<ans<<endl;
}
关于并查集：并查集(13张图解)--擒贼先擒王_算法并查集嫌疑人问题-CSDN博客