codeforces Connected Components（寻找补图的连通块）

http://codeforces.com/contest/920/problem/E

E. Connected Components?

time limit per test

memory limit per test

input

output

n vertices and 

 edges. Instead of giving you the edges that exist in the graph, we give you m unordered pairs (x, y) such that there is no edge between x and y, and if some pair of vertices is not listed in the input, then there is an edge between these vertices.

X such that for every two vertices from this set there exists at least one path in the graph connecting these vertices, but adding any other vertex to X

Input

n and m (1 ≤ n ≤ 200000, 

).

m lines follow, each containing a pair of integers x and y (1 ≤ x, y ≤ n, x ≠ y) denoting that there is no edge between x and y. Each pair is listed at most once; (x, y) and (y, x) are considered the same (so they are never listed in the same test). If some pair of vertices is not listed in the input, then there exists

Output

k

k

Example

input

5 51 23 4 3 2 4 2 2 5

output

21 4

【题意】

输入一个n点m边的无向图，求其补图的连通块。

补图：在完全图中，去掉原图中的边。

【分析】

在原图中不相接的两个点，在补图中肯定相连。因此，对一个点u而言，标记其所有的邻接边，那么没被标记的点，就是补图中u的邻接点。找到u的补图中的邻接点之后，再由找到的这些点用同样的方法找到邻接点，从而找出整个连通块。很明显BFS维护最合适。

【代码】

#include<bits/stdc++.h>
#define mset(a,i) memset(a,i,sizeof(a))
using namespace std;
const int N=202020;
struct node{
    int t,next;
}e[N<<2];
int head[N],cnt;
void add(int u,int v)
{
    e[cnt]=node{v,head[u]};
    head[u]=cnt++;
}
bool vis[N],vi[N];
int d[N];
int ans[N];
int main()
{
    int n,m,u,v;
    while(cin>>n>>m)
    {
        mset(head,-1);cnt=0;
        while(m--)
        {
            scanf("%d%d",&u,&v);
            add(u,v);
            add(v,u);
        }
        for(int i=1;i<=n;i++)d[i]=i;
        int dtop=n,top=0;

        mset(vis,0); //标记已完成的点
        mset(vi,0);  //标记相邻点
        queue<int>q;
        for(int j=1;j<=n;j++)if(!vis[j])
        {
            ans[top++]=0; //新连通块,bfs找到此连通块所有点
            q.push(j);
            while(!q.empty())
            {
                int u=q.front();q.pop();
                vis[u]=1;
                ans[top-1]++;
                for(int i=head[u];~i;i=e[i].next) //当前图的邻接点
                    if(!vis[e[i].t])
                        vi[e[i].t]=1;
                for(int i=1;i<=dtop;)
                {
                    if(!vis[d[i]]&&!vi[d[i]]) //反图的相邻点
                    {
                        q.push(d[i]);
                        d[i]=d[dtop--]; //删除点d[i]（优化）
                    }
                    else vi[d[i++]]=0;
                }
            }
        }
        sort(ans,ans+top);
        printf("%d\n",top);
        for(int i=0;i<top;i++)
            printf("%d%c",ans[i],i<top-1?' ':'\n');
    }
}