河南省建设监理网站百度应用下载安装

链接：登录—专业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博客