LOJ-10099（点双联通）

题目链接：传送门

思路：

如果图是点双联通的，即没有割点，直接从图中随意选两个点即可；

如果有一个割点，删除割点，求连通块的个数即可（在每个连通块内新建一个营救点）。

如果有多个割点，则可以通过其他割点到达，就不用新建营救点。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<stack>

#include<queue>

using namespace std;

typedef long long LL;

const int maxn = ;

int num[maxn],low[maxn],vis[maxn],gedian[maxn],tim,pt,root;

vector <int> vc[maxn];

vector <int> block[maxn];

stack <int> st;

int MAX(int x,int y)

{

    return x>y?x:y;

}

int MIN(int x,int y)

{

    return x<y?x:y;

}

void Init()

{

    memset(vis,,sizeof(vis));

    memset(num,,sizeof(num));

    memset(low,,sizeof(low));

    memset(gedian,,sizeof(gedian));

    for(int i=;i<maxn;i++) vc[i].clear(),block[i].clear();

    tim=;pt=;

    while(!st.empty()) st.pop();

}

void Tarjan(int u,int pre)

{

    num[u]=low[u]=++tim;

    vis[u]=;

    st.push(u);

    int v,i,cnt=;

    for(i=;i<vc[u].size();i++){

        v=vc[u][i];

        if(!vis[v]){

            cnt++;

            Tarjan(v,u);

            low[u]=MIN(low[u],low[v]);

            if((u==root&&cnt>)||(u!=root&&num[u]<=low[v])) gedian[u]=;

            if(num[u]<=low[v]){

                pt++;

                int kk;

                do{

                    kk=st.top();

                    block[pt].push_back(kk);

                    st.pop();

                }while(!st.empty()&&kk!=v);

                block[pt].push_back(u);

            }

        }

        else low[u]=MIN(low[u],num[v]);

    }

}

int main(void)

{

    int n,m,x,y,i,j,T=;

    while(~scanf("%d",&m)&&m){

        Init();

        n=;

        for(i=;i<=m;i++){

            scanf("%d%d",&x,&y);

            n=MAX(n,MAX(x,y));

            vc[x].push_back(y);

            vc[y].push_back(x);

        }

        for(i=;i<=n;i++)

        if(vis[i]==){

            root=i;

            Tarjan(i,-);

        }

        int art,len;

        LL ans=,artnum=;

        for(i=;i<=pt;i++){

            art=;len=block[i].size();

            for(j=;j<len;j++)

                if(gedian[block[i][j]]) art++;

            if(art==) ans+=,artnum=artnum*len*(len-)/;

            else if(art==) ans++,artnum=artnum*(len-);

        }

        printf("Case %d: %lld %lld\n",T++,ans,artnum);

    }

    return ;

}