鏈接：登錄—專業(yè)IT筆試面試備考平臺_?？途W(wǎng)
來源：牛客網(wǎng)
?

題目描述

“サーヴァント、キャスター、Medea?！?-紫魔法師

給出一棵仙人掌(每條邊最多被包含于一個環(huán)，無自環(huán)，無重邊，保證連通)，要求用最少的顏色對其頂點染色，滿足每條邊兩個端點的顏色不同，輸出最小顏色數(shù)即可

輸入描述:

第一行包括兩個整數(shù)n,m，表示頂點數(shù)和邊數(shù)
n <= 100000, m <= 200000
接下來m行每行兩個整數(shù)u,v，表示u,v之間有一條無向邊，保證數(shù)據(jù)合法

輸出描述:

一行一個整數(shù)表示最小顏色數(shù)

#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;
}

?關(guān)于并查集：并查集(13張圖解)--擒賊先擒王_算法并查集嫌疑人問題-CSDN博客