$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

tarjan 缩点（点的双连通分量）

1. 如果是一个点，就直接放入该连通分量
2. 如果不是根结点或者删除该点后连通块个数大于2，则记录该点为割点
3. 把栈中元素弹出，一直弹到割点的下一个点，割点要独自放入该连通分量中，因为割点不只属于一个连通分量

思路：

1. 对每个点的双连通分量进行 tarjan 缩点
2. 枚举所有的连通分量，并统计该连通分量内割点的个数
3. 如果无割点，则随便选两个点放出口，如果有一个割点，则随便选一个点放出口（割点除外）

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ULL;

const int N = 1010, M = 510;

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

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

void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u;

    //只有一个点
    if(u==root&&h[u]==-1)
    {
        dcc_cnt++;
        dcc[dcc_cnt].push_back(u);
        return;
    }

    int cnt=0;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);

            if(dfn[u]<=low[j])
            {
                //删除该点后得到的新的连通块个数
                cnt++;

                //不是根节点或者删除该点后连通块个数大于 2，符合割点条件
                if(u!=root||cnt>1) cut[u]=true;

                //点的连通分量的基本操作
                dcc_cnt++;
                int y;
                do {
                    y=stk[top--];
                    dcc[dcc_cnt].push_back(y);
                } while(y!=j);

                //注意：割点只需加一次
                dcc[dcc_cnt].push_back(u);
            }
        }
        else low[u]=min(low[u],dfn[j]);
    }
}

int main()
{
    int T=1;
    while(cin>>m,m)
    {
        //数据初始化，我自己写的时候想半天呜呜呜
        for(int i=1;i<=dcc_cnt;i++) dcc[i].clear();
        n=idx=timestamp=dcc_cnt=top=0;
        memset(h,-1,sizeof h);
        memset(dfn,0,sizeof dfn);
        memset(cut,0,sizeof cut);

        while(m--)
        {
            int a,b;
            cin>>a>>b;
            n=max(n,max(a,b));
            add(a,b),add(b,a);
        }

        //把每个点的双连通分量缩点
        for(root=1;root<=n;root++)
            if(!dfn[root])
                tarjan(root);

        //枚举所有的连通分量
        ULL res=0,num=1;
        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)
            {
                //随便选两个点放
                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;
        }

        printf("Case %d: %llu %llu\n",T++,res,num);
    }

    return 0;
}