Tarjan求点双连通分量,缩点

HNOI2012矿场搭建

题意

( 给定一个无向图，可能不连通，如果图中某个点坍塌，要求其他点一定能从某个出口逃出，\ 问:至少设计几个出口和不同的最小救援出口的设置数量。 )

解析

( 设最小出口数为ans,方案数为num\ 分别分析每一个连通块，分析每一个连通块中的v-dcc\ 1.容易得到ans>=2\ 2.\ quad 1.如果v\_dcc中没有割点\ quadquad 1.1如果v-dcc中只有一个点,那么在该点设置一个出口\ quadquad 1.2如果v-dcc中点的数量>1，因为没有割点，v\_dcc无法和外界连通，因此内部至少需要两个出口，\ quadquad v-dcc中的所有点才能自救,ans+=2,num*=C(v\_dcc.size(),2);\ quad 2.如果v\_dcc有一个割点\ quadquad 那么可以想到只要在非割点处建立一个出口，无论是割点坍塌，还是出口坍塌，v-dcc中的点都可以逃走\ quadquad ans++,num+=C(v\_dcc.size()-1),\ quad 3.如果v\_dcc有多个割点\ quad quad 无论是割点还是v\_dcc内部非割点坍塌，v-dcc都能通过至少一个割点逃到别的v-dcc中去.\ quad quad不用设置出口\ )

( 貌似发现了蓝书上(P404)求low数组的错误(雾) )

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;

const int N=510*2,M=1010;

int n,m,h[N],ne[M],e[M],idx;
int dfn[N],low[N],tim;
int stack[N],top;
vector<int>dcc[N];
int dcc_cnt,root;
bool cut[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void tarjan(int x)
{
    low[x]=dfn[x]=++tim;
    stack[++top]=x;
    
    if(x==root&&h[x]==-1)
    {
        dcc[++dcc_cnt].push_back(x);
        return ;
    }
    int cnt=0;
    for(int i=h[x];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[x]=min(low[x],low[j]);
            if(dfn[x]<=low[j])
            {
                cnt++;
                if(x!=root||cnt>1)
                    cut[x]=true;
                int y;
                dcc_cnt++;
                do{
                
                    y=stack[top--];
                    dcc[dcc_cnt].push_back(y);
                }while(y!=j);
                dcc[dcc_cnt].push_back(x);
            }
        }
        else low[x]=min(low[x],dfn[j]);
    }
}

int main()
{
    int t=1;
    while(cin>>m,m)
    {
        for(int i=1;i<=dcc_cnt;i++)
            dcc[i].clear();
        idx=tim=top=dcc_cnt=n=0;
        memset(h,-1,sizeof h);
        memset(dfn,0,sizeof dfn);
        memset(cut,0,sizeof cut);
        while(m--)
        {
            int a,b;cin>>a>>b;
            add(a,b),add(b,a);
            n=max(n,a),n=max(n,b);
        }
        for(root=1;root<=n;root++)
            if(!dfn[root])
                tarjan(root);
        
        int res=0;
        unsigned long long num=1;
        cout<<dcc_cnt<<endl;
        cout<<"---"<<endl;
        for(int i=1;i<=n;i++)
            cout<<i<<" "<<dfn[i]<<" "<<low[i]<<endl;
        cout<<endl;
        for(int i=1;i<=dcc_cnt;i++)
        {
            int cnt=0;
            for(int j=0;j<dcc[i].size();j++)
            {
                if(cut[dcc[i][j]])
                    cnt++;
            }
            if(cnt==0)
            {
                if(dcc[i].size()>1)
                    res+=2,num*=dcc[i].size()*(dcc[i].size()-1)/2;
                else
                    res++;
            }
            else if(cnt==1)
                res++,num*=dcc[i].size()-1;
            cout<<"cnt="<<cnt<<endl;
        }
        printf("Case %d: %d ",t++,res);
        cout<<num<<endl;
        cout<<top<<" "<<stack[top]<<endl;
    }
    return 0;
}