Mining Your Own Business

//无向图的双连通分量
//每次调用前手动清空vector<int> G
//使用时只更新G完成构图
//bcc_cnt从1开始计数

//pre[]表示点在DFS树中的先序时间戳
//iscut[]表示点是否为割点
//bccno[]表示点所在的双连通分量编号
//bcc_cnt表示双连通分量个数
//vector<int> G保存每个点相邻的下一个点序号
//vector<int> bcc保存每个双连通分量的点集,算法运行过程动态清空
//stack<Edge> S是算法用到的栈
const int MAXV = 51000;
const int MAXE = 51000;

int pre[MAXV], iscut[MAXV], bccno[MAXV], dfs_clock, bcc_cnt; // 割顶的bccno无意义
struct Edge
{
    int u, v;
};
vector<int> G[MAXV], bcc[MAXV];
stack<Edge> S;

int dfs(int u, int fa)
{
    int lowu = pre[u] = ++dfs_clock;
    int child = 0;
    for(int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i];
        Edge e = (Edge){u, v};
        if(!pre[v])   // 没有访问过v
        {
            S.push(e);
            child++;
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv); // 用后代的low函数更新自己
            if(lowv >= pre[u])
            {
                iscut[u] = true;
                bcc_cnt++;
                bcc[bcc_cnt].clear();
                for(;;)
                {
                    Edge x = S.top();
                    S.pop();
                    if(bccno[x.u] != bcc_cnt)
                    {
                        bcc[bcc_cnt].push_back(x.u);
                        bccno[x.u] = bcc_cnt;
                    }
                    if(bccno[x.v] != bcc_cnt)
                    {
                        bcc[bcc_cnt].push_back(x.v);
                        bccno[x.v] = bcc_cnt;
                    }
                    if(x.u == u && x.v == v) break;
                }
            }
        }
        else if(pre[v] < pre[u] && v != fa)
        {
            S.push(e);
            lowu = min(lowu, pre[v]); // 用反向边更新自己
        }
    }
    if(fa < 0 && child == 1) iscut[u] = 0;
    return lowu;
}

void find_bcc(int n)
{
    // 调用结束后S保证为空，所以不用清空
    memset(pre, 0, sizeof(pre));
    memset(iscut, 0, sizeof(iscut));
    memset(bccno, 0, sizeof(bccno));
    dfs_clock = bcc_cnt = 0;
    for(int i = 0; i < n; i++)
        if(!pre[i]) dfs(i, -1);
};

int main()
{
//    freopen("in.txt", "r", stdin);
    int n, a, b, kase = 1;
    while (~RI(n) && n)
    {
        REP(i, MAXV) G[i].clear();

        int Max = 0;
        REP(i, n)
        {
            RII(a, b); a--; b--;
            Max = max(Max, max(a, b));
            G[a].push_back(b);
            G[b].push_back(a);
        }
        find_bcc(Max);
        LL ans = 1, cnt = 0;
        if (bcc_cnt == 1)
        {
            LL m = bcc[1].size();
            ans = m * (m - 1) / 2;
            cnt = 2;
        }
        else
        {
            FE(i, 1, bcc_cnt)
            {
                int tcnt = 0;
                REP(j, bcc[i].size())
                {
                    if (iscut[bcc[i][j]])
                        tcnt++;
                }
                if (tcnt == 1)
                {
                    ans *= (bcc[i].size() - 1);
                    cnt++;
                }
            }
        }
        printf("Case %d: ", kase++);
        cout << cnt << ‘ ‘ << ans << endl;
    }
    return 0;
}