题解 P3452 【[POI2007]BIU-Offices】

孑思 · 2018-10-05 10:53:47 · 题解

这是一个求原图的补图联通块个数的题

我们可以知道如果一个点在原图中不能到达另一个点

那么这个点一定可以在补图中到达那个点

但是原图可以到达的点补图不一定不能到达

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
bool vis[100010],cov[100010];
int cnt,head[100010],nxt[4000100],var[4000100];
int nex[100010],last[100010];
int st[100010],ans;
int n,m;
queue<int> q;
void add(int x,int y) {
    cnt++;
    var[cnt]=y;
    nxt[cnt]=head[x];
    head[x]=cnt;
}//链式向前星，蒟蒻不会vector QWQ
void del(int x) {
    nex[last[x]]=nex[x];
    last[nex[x]]=last[x];
}//删除链表中的某个元素
int main() {
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=1; i<=m; i++) {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);//建图
    }
    nex[0]=1;
    for(int i=1; i<n; i++) {
        last[i+1]=i;
        nex[i]=i+1;
    }
    //可以理解为链表，访问的时候可以快一点
    for(int i=1; i<=n; i++) {
        if(!vis[i]) { 
        //如果没被访问过
            st[++ans]=1;//新开一个联通块
            vis[i]=true;//标记
            q.push(i);//入队
            del(i);//删除这个点
            while(!q.empty()) {
                int x=q.front();
                q.pop();
                for(int j=head[x]; j; j=nxt[j]) {
                    if(!vis[var[j]]) { 
                    //如果原图可以到达的点没有访问过
                        cov[var[j]]=true;
                        //标记，原图可以访问
                    }
                }
                for(int j=nex[0]; j; j=nex[j]) {
                    if(!cov[j]) { 
                    //访问不到的全都入队，因为在补图里可以访问到
                        vis[j]=true;
                        //这个点在补图里访问过了
                        st[ans]++;
                        //联通块里的点的个数++；
                        del(j);
                        //删除这个点
                        q.push(j);
                        //入队
                    } else cov[j]=false; 
                    //如果在原图中可以访问到，那就没他什么事了，恢复原样吧
                }
            }
        }
    }
    sort(st+1,st+ans+1);//排序一下
    printf("%d\n",ans);
    for(int i=1; i<=ans; i++) {
        printf("%d ",st[i]);
    }
    return 0;
    //return 0不知道有没有必要，这几天Claris上课标程永远没有return 0，但是蒟蒻又不敢不打，瑟瑟发抖
}

感谢 奔波儿霸 指出错误