bzoj2730矿场搭建——点双连通分量

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2730

首先一遍tarjan找出割点，将图缩点，这些大点中如果有只包含一个割点的，那么如果这个割点被去掉，则这个大点与图不连通，所以这个大点内必须有一个出口；

而如果没有割点，需要建两个出口，以防止一个出口点被去掉；

方案数就是放出口的大点的size乘积；没有割点则方案数为C(m,2)；

注意自己记录点数。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

using namespace std;

int const MAXN=;

vector<int>dcc[MAXN];

int t,n,m,siz,tim,ct,head[MAXN],dfn[MAXN],low[MAXN],num,k;

long long ans;

bool vis1[MAXN],vis2[MAXN],cut[MAXN];

struct N{

    int to,next;

    N(int t=,int n=):to(t),next(n) {}

}edge[MAXN<<];

void add(int x,int y)

{

    edge[++ct]=N(y,head[x]);head[x]=ct;

    edge[++ct]=N(x,head[y]);head[y]=ct;

}

void tarjan(int x,int f)

{

    dfn[x]=low[x]=++tim;

    int fl=;

    for(int i=head[x],u;i;i=edge[i].next)

    {

        if(edge[i].to==f)continue;

        if(!dfn[u=edge[i].to])

        {

            fl++;

            tarjan(u,x);

            low[x]=min(low[x],low[u]);

            if(low[u]>=dfn[x])/*fl++,*/cut[x]=;

        }

        else low[x]=min(low[x],dfn[u]);

    }

    if(!f&&fl==)cut[x]=;

}

int dfs(int x)

{

    int siz=;

    vis1[x]=;

    for(int i=head[x],u;i;i=edge[i].next)

    {

        if(vis1[u=edge[i].to]||vis2[u])continue;

        if(!cut[u])siz+=dfs(u);

//        if(!cut[u])siz++,dfs(u);

        else if(!vis2[u])vis2[u]=,num++;

    }

    return siz;

}

int main()

{

    while(scanf("%d",&n)==)

    {

        if(!n)return ;

        t++;ct=;

        tim=;m=;//

        memset(dfn,,sizeof dfn);

        memset(low,,sizeof low);

        memset(cut,,sizeof cut);

        memset(head,,sizeof head);

        memset(vis1,,sizeof vis1);

        int x,y;

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

        {

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

            add(x,y);

            m=max(m,x);m=max(m,y);

        }

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

            if(!dfn[i])tarjan(i,);

        ans=;k=;

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

            if(!vis1[i]&&!cut[i])//不能是割点

            {

                num=;

                memset(vis2,,sizeof vis2);

                siz=dfs(i);

                if(num==)k++,ans*=siz;

            }

        if(!k)k=,ans=(long long)m*(m-)/;//m!

        printf("Case %d: %d %lld\n",t,k,ans);

    }

    return ;

}