[K分图判定]长安大学第二届ACM校赛题解 K-partite Graph

描述
We are all familiar with bipartite graph, actually it can be extended to multipartite graph.

If vertices of an undirected graph G can be divided into exactly k(k≥2) non-empty sets, and for each pair of vertices u and v, there exists an edge (u, v) if and only if they are from different sets, then G is defined as a complete k-partite graph.

Given an undirected graph G with n vertices and m edges, judge whether it is a complete k-partite graph.

输入
The first line contains an integer number T, the number of test cases.

For each test case :

The first line contains two integers n and m(1≤n≤1000,0≤m≤n×(n−1)2), the number of vertices and edges.

i-th of each next m lines contains two integers ui ans vi, which means there exists an undirected edge between ui and vi (1≤ui,vi≤n,ui≠vi).

It’s also guaranteed that no duplicated edges in the input.

输出
For each test case :

print a number k if G is a complete k-partite graph(k≥2), print “0”(without quotation) otherwise.

样例输入1 复制
3
1 0
3 3
1 2
2 3
3 1
6 6
1 5
1 6
2 4
2 6
3 4
3 5
样例输出1
0
3
0

利用并查集对K分图进行判定，不相连的边放入并查集内 。然后在进行判断其是不是K分图。

#include<bits/stdc++.h>
using namespace std;
#define Rep(i,n) for(int i=0;i<n;i++)
#define For(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define F (1000000007)
#define MAXN (1011)
#define MEM(x) memset(x,0,sizeof(x));
int T;
int n,m;
int f[MAXN][MAXN];
int fa[MAXN];
int getfa(int x) {
    if (fa[x]==x) return x;
    return fa[x]=getfa(fa[x]);
}
void uni(int x,int y) {
    x=getfa(x);y=getfa(y);
    if (x!=y) fa[x]=y;
}
int check() {
    for(int i=1;i<=n;i++)
        getfa(i);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i-1;j++)
        {
            if (f[i][j] &&fa[i]==fa[j]) return 0;
            if (!f[i][j] &&fa[i]!=fa[j]) return 0;
        }
    }
    int p=0;
    for(int i=1;i<=n;i++)
        if (fa[i]==i)
            p++;
    if (p<2) p=0;
    return p;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);MEM(f)
        For(i,n) fa[i]=i;
        For(i,m) {
            int a,b;
            scanf("%d%d",&a,&b);
            f[a][b]=f[b][a]=1;
        }
        for(int i =1 ;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                if (!f[i][j]) {
                    uni(i,j);
                }
            }
        }
        printf("%d\n",check());
    }
    return 0;
}