hdu 4338 Simple Path 点双连通分量的两个问题

本文从WordPress迁移而来, 查看全部WordPress迁移文章

hdu 4338 和 uva 12616 差不多一样，主要是都使用相同的方法来进行缩点和拆点建树

关于具体的步骤，可以参考 uva 12616 的题解，这里只说一下本题

本题的区别是，更改cal函数

uva中，comnum是指，一个连通块中，非割点数的数量

hdu中，comnum是指，整个连通块的点数

那么在统计过程中，肯定会出现重复统计割点的情况，本题采用的是减掉重复割点的方法，在treedp中需要继续路径中割点的数量，在求出lca后，减掉路径上的割点数即可

求lca的方法，用在线倍增算法（不是转化为RMQ），模板来自AcRush

#pragma comment(linker, "/STACK:10240000000,10240000000")
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iterator>
#include <vector>
#include <set>
#include <stack>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define two(X) (1<<(X))
#define contain(S,X) (((S)&two(X))!=0)
#define N 100000
#define M 200000

class BccCut{
private:
    //com[id]:连通分量号为id的块中，包含了哪些原图中的点
    set<int>com[N+10]; 
    //belong[u]:原图中的点u属于哪些连通分量，若是非割点，只属于一个，如果是割点，可能属于多块
    set<int>belong[N+10]; 

    //Tarjan
    int root,dcnt,bcnt,top,dfn[N+10],low[N],stack[M+M+10];
    int iscut[N+10]; //是否为割点
    vector<int>cp; //保存所有割点

    //构图
    int n,tot,head[N+10];
    struct edge{
        int u,v,next;
        bool used; //通用写法，有无重边都可处理
    }e[M+M+10];

    //建树，邻接表，拆点后，点数最多为N+N，边数=点数-1，另外无向边，翻倍
    int nt,tott,tree[N+N+10];
    struct edget{
        int u,v,next;
    }et[(N+N+10)<<1];

public:
    BccCut(){}
    ~BccCut(){}

    void init(int nn){
        n = nn; tot = 0; cl(head,-1);
    }

    //构图
    void add(int u,int v){
        e[tot].u = u; e[tot].v = v; e[tot].used = false;
        e[tot].next = head[u]; head[u] = tot++;
    }

    //Tarjan内部，统计一个点双连通分量
    void get_bcc(int key){
        ++bcnt;
        while(true){
            int k = stack[top--];
            int u = e[k].u , v = e[k].v;
            belong[u].insert(bcnt);
            belong[v].insert(bcnt);
            com[bcnt].insert(u);
            com[bcnt].insert(v);
            if(u == key) break;
        }
    }

    //Tarjan缩点,递归版本
    void tarjan(int u){
        dfn[u] = low[u] = ++dcnt;
        //stack[++top] = u;
        int son = 0;
        for(int k = head[u]; k != -1; k = e[k].next){
            if(e[k].used) continue;
            e[k].used = e[k^1].used = true; //有无重边都可以处理
            stack[++top] = k;
            int v = e[k].v;
            if(!dfn[v]){
                son++;
                tarjan(v);
                low[u] = min(low[u] , low[v]);
                //当u为本次遍历的根时，该条件不足以说明u是割点，因此最后有个特判
                if(low[v] >= dfn[u]){
                    iscut[u] = true;
                    get_bcc(u); //从栈中取出连通分量
                }
            }
            else low[u] = min(low[u],dfn[v]);
        }
        //特判
        if(u == root && son < 2) iscut[u] = false;
        //最后才保存割点
        if(iscut[u]) cp.pb(u);
    }

    //求Bcc
    void BCC(){
        cl(dfn,0); 
        cl(iscut,false);
        cp.clear();
        dcnt = bcnt = top = 0;
        for(int i = 1; i <= n; i++){
            belong[i].clear();
            com[i].clear();
        }
        for(int u = 1; u <= n; u++){
            if(dfn[u]) continue;
            root = u;
            tarjan(u);
        }
    }

    //缩点后建树，这个建树，包含了拆点的过程
    //点双连通分量建树并不是太多，如果要建树，可能都需要用上拆点
    //所以把这个函数归为模板的一部分
    void addt(int u,int v){
        et[tott].u = u; et[tott].v = v;
        et[tott].next = tree[u]; tree[u] = tott++;
    }
    
    void rebuild(){
        //树的顶点数，就是连通块数，加上割点数（每个割点拆点）
        nt = bcnt + cp.size();
        tott = 0; cl(tree,-1);
        int size = cp.size();
        for(int i = 0; i < size; i++){
            int CP = cp[i];
            int __uu__ = CP + N; //虚构一个树节点__uu__
            set<int>::iterator it;
            for(it = belong[CP].begin(); it != belong[CP].end(); it++){ 
                //看看哪些块中包含了这个割点
                //用__uu__将这个块连起来
                int id = *it; //块
                addt(__uu__,id);
                addt(id,__uu__);
            }
        }
    }


    void cal();
    void treedp();
    void query();
    void dfs(int u,int par);
    int judge(int &x , int &y);
    int solve(int x,int y,int lca);
    int LCA(int x,int y);

private:
    int comnum[N+N+10];
    int ID[N+N+10],__id__;
    int d[N+N+10],fa[N+N+10],sc[N+N+10],__sc__[N+N+10];
    int f[N+N+10][30];
    bool vis[N+N+10];
};

void BccCut::cal(){
    cl(comnum,0);
    for(int i = 1; i <= bcnt; i++)
        comnum[i] = com[i].size();
}

void BccCut::dfs(int u,int par){
    ID[u] = __id__;
    fa[u] = par;
    vis[u] = true;
    if(par == -1){
        d[u] = 0;
        sc[u] = comnum[u];
        if(u > N) __sc__[u] = 1;
        else __sc__[u] = 0;
    }
    else{
        d[u] = d[par] + 1;
        sc[u] = sc[par] + comnum[u];
        if(u > N) __sc__[u] = __sc__[par] + 1;
        else __sc__[u] = __sc__[par];
        f[u][0] = fa[u];
        for(int w = 1; two(w) <= d[u]; w++)
            f[u][w] = f[f[u][w-1]][w-1];
    }
    for(int k = tree[u]; k != -1; k = et[k].next){
        int v = et[k].v;
        if(vis[v]) continue;
        dfs(v,u);
    }
}

void BccCut::treedp(){
    cl(f,0);
    cl(vis,false);
    cl(ID,-1);
    __id__ = 0;
    for(int i = 0; i < cp.size(); i++){
        int CP = cp[i];
        int __uu__ = CP + N;
        if(vis[__uu__]) continue;
        __id__++;
        dfs(__uu__,-1);
    }
}

int BccCut::judge(int &x,int &y){
    if(x == y){ //同一个点
        printf("%d\n",n-1);
        return -1;
    }
    set<int>::iterator it;
    if(iscut[x]) x += N;
    else if(belong[x].size() == 0) x = -1; //孤立点
    else x = *(it=belong[x].begin());
    if(iscut[y]) y += N;
    else if(belong[y].size() == 0) y = -1; //孤立点
    else y = *(it=belong[y].begin());

    if(x == -1 || y == -1){ //有一个是孤立点
        printf("%d\n",n);
        return -1;
    }
    if(ID[x] != ID[y]){ //不连通
        printf("%d\n",n);
        return -1;
    }
    else if(ID[x] == -1 && x == y){
        printf("%d\n",n-comnum[x]);    
        return -1;
    }
    else if(ID[x] == -1 && x != y){
        printf("%d\n",n);
        return -1;
    }
    else return 0;
}

int BccCut::solve(int x,int y,int lca){
    //return sc[x] + sc[y] -2*sc[lca] + comnum[lca] - __sc__[x] - __sc__[y] + 2*__sc__[lca];
    int sum1 = sc[x] + sc[y] - 2*sc[lca] + comnum[lca];
    int t1,t2,t3;
    if(x > N) t1 = __sc__[x] - 1;
    else t1 = __sc__[x];
    if(y > N) t2 = __sc__[y] - 1;
    else t2 = __sc__[y];
    if(lca > N) t3 = __sc__[lca] - 1;
    else t3 = __sc__[lca];

    int sum2 = t1 + t2 - 2*t3;
    if(lca > N) sum2 -= 1;
    int sum = sum1 - sum2;
    return sum;
}

int BccCut::LCA(int a,int b)
{
    //if(a == b) return a;
    if (d[a]>d[b]) swap(a,b);
    if (d[b]>d[a])
    {
        int e=d[b]-d[a];
        for (int w=0;w<20;w++) 
            if (contain(e,w)){
                b=f[b][w];
            }
    }
    if (a==b) return a;
    int h=d[a]-1;
    for (int w=19;w>=0;w--) if (contain(h,w))
    {
        int pa=f[a][w];
        int pb=f[b][w];
        if (pa==pb)
            h=two(w)-1;
        else
        {
            h-=two(w);
            a=pa;
            b=pb;
        }
    }
    return f[a][0];
}

void BccCut::query(){
    int Q;
    scanf("%d",&Q);
    while(Q--){
        int x,y;
        scanf("%d%d",&x,&y);
        x++; y++;
        if(judge(x,y) == -1) continue;
        int lca = LCA(x,y);
        int ans = solve(x,y,lca);
        printf("%d\n",n-ans);
    }
}

int main(){
    BccCut *G = new BccCut();
    int cas = 0,n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        printf("Case #%d:\n",++cas);

        G->init(n);
        while(m--){
            int u,v;
            scanf("%d%d",&u,&v);
            u++; v++;
            G->add(u,v);
            G->add(v,u);
        }
        G->BCC();
        G->cal();
        G->rebuild();
        G->treedp();
        G->query();

        puts("");
    }
    delete(G);
    return 0;
}