BZOJ 2079：Poi2010 Guilds——並查集判斷二分圖可行性

題目描述

無向圖，需紅黑染色使每個節點及其鄰居至少有一紅一黑。判斷是否可行。

關鍵結論

連通塊大小 ≥ 2 總可構造：任取生成樹，按層次二分染色（深度奇偶）。只有孤立點（度為 0）無法滿足條件。

算法

1. 並查集維護連通塊大小
2. 讀入邊合併
3. 檢查是否存在大小為 1 的連通塊

C++ 實現

#include <cstdio>
#include <cstring>
using namespace std;
const int M = 200200;
int fa[M], sz[M];
int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); }
void unite(int x, int y) {
    x=find(x); y=find(y);
    if(x!=y) fa[x]=y, sz[y]+=sz[x];
}
int main() {
    int n,m; scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) fa[i]=i, sz[i]=1;
    for(int i=0,u,v;i

複雜度

時間：O((n+m) α(n))
空間：O(n)