链表加bfs求补图联通块

时间:2021-01-22 15:48:28

https://oj.neu.edu.cn/problem/1387

给一个点数N <= 100000, 边 <= 1000000的无向图,求补图的联通块数,以及每个块包含的点数

由于点数太大,补图会是稠密图,甚至建立补图都要O(n^2),只能挖掘一下联通块,bfs,补图的性质,从原图入手求补图的联通块:

 

在原图中不直接相邻的点,在补图中一定属于同一个联通块

每个点只属于一个联通块,所以找好一个联通块之后可以删去这个联通块的所有点,把图规模缩小

 

这样子:1.准备一个集合放所有未探索的点,初始化时将1~N放进去

2.从集合中取一点放入队列(新的联通块)

3.当队列不为空时,从队列中取一个点u并弹出,将原图中与u直接相连的点标记;遍历集合,将在集合中的(即未探索的)并且未被标记的点(这些点属于本联通块)入队并从集合中删去,将标记删去。重复执行直到队列为空

4.集合不为空转2,为空结束

考虑有删除操作和时间问题,集合的实现当然是选择链表,用数组实现的双向链表即可 

 

优化有两个:一是通过原图找补图的联通块;二是把搜过的点删除,这样每次找未标记的点时比起从1循环到N更优(常数优化(误))

链表加bfs求补图联通块链表加bfs求补图联通块
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
const int maxn = 1e5+100, maxm = 1e6+100, inf = 0x3f3f3f3f;
struct lnk{
    int val;
    int pre, nxt;
}lk[maxn];
struct edge{
    int v, nxt;
}e[maxm*2];
int head[maxn], tot, block_cnt, n, m;
int adj[maxn], vis[maxn], num[maxn];
void addedge(int u, int v){
    e[tot] = (edge){v, head[u]};
    head[u] = tot++;
}
void dele(int x){
    lk[lk[x].nxt].pre = lk[x].pre;
    lk[lk[x].pre].nxt = lk[x].nxt;
}
void src(){
    for(int i = 1; i <= n; i++){
        vis[i] = adj[i] = 0;
    }
    queue<int>Q;
    block_cnt = 0;
    while(lk[0].nxt != -1){
        //puts("blk++");
        Q.push(lk[0].nxt);
        //printf("take %d\n", lk[0].nxt);
        vis[lk[lk[0].nxt].val] = 1;
        dele(lk[0].nxt);
        block_cnt++;
        num[block_cnt] = 1;
        while(!Q.empty()){
            int x = Q.front();
            x = lk[x].val;
            //printf("%d\n", x);
            Q.pop();
            for(int i = head[x]; ~i; i = e[i].nxt){
                int v = e[i].v;
                adj[v] = 1;
            }
            for(int i = lk[0].nxt; ~i; i = lk[i].nxt){
                int w = lk[i].val;
                if(!vis[w] && !adj[w]){
                    Q.push(w);
                    vis[w] = 1;
                    dele(i);
                    num[block_cnt]++;
                }
            }
            for(int i = head[x]; ~i; i = e[i].nxt){
                int v = e[i].v;
                adj[v] = 0;
            }
        }
    }
}
int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++)
            head[i] = -1;
        tot = 0;
        while(m--){
            int u, v;
            scanf("%d%d", &u, &v);
            addedge(u, v);
            addedge(v, u);
        }
        for(int i = 1; i <= n; i++){
            lk[i].val = i;
            lk[i].pre = i-1;
            lk[i].nxt = i+1;
        }
        lk[n].nxt = -1;
        lk[0].nxt = 1;
        src();
        sort(num+1, num+block_cnt+1);
        printf("%d\n", block_cnt);
        for(int i = 1; i <= block_cnt; i++){
            printf("%d%c", num[i], i == block_cnt ? '\n' : ' ');
        }
    }
    return 0;
}
/*
 3
 5 7
 1 2
 1 3
 1 4
 1 5
 2 3
 2 4
 2 5
 6 9
 1 4 1 5 1 6
 2 4 2 5 2 6
 3 4 3 5 3 6
 3 3
 1 2 2 3 3 1
 
*/
View Code