tarjan、割点、分类讨论

题意：

分析：

这题很容易让我们想到割点。
这并不难，但是细节上的处理于分类讨论才是这道题的难点。

我们想想如果一个连通块，他有一个割点。

那么，我们一定要在他被割点分开的两个连通块中放置救援出口。
而放置的方案数就是两边的点数相乘，割点不算！

如果，他有两个以上的割点呢？

比如：

图中箭头指向割点处。两边呵中间为割点分开的连通块。

如果是你，你会在哪里防止救援出口呢？
会三个连通块都放置吗？
不会的！！
我们只需在最两端放置就可以了！
那这种呢：

我们同样还是最两边放置的！！
直接给出结论：我们只在有一个割点的连通块内放置一个救援出口(没有连通块的还没讨论)
这是一个简单的道理，画画图就可以得出。做题时更靠感觉，思维，要敏感！

那么，队友割点的连通块，如果割点数为1我们放置，如果割点数大于2我们跳过！
（记住，这里的连通块是指，割点断开后形成的，不是最初的）

ok，那我们再来讨论一个割点都没有时

那么，我们时一定要放2个的。因为放1个的话刚好就是这个点塌了咋办？！
所以放两个！放置方案就是C(n,2)

至此，我们全部讨论完毕！！
方案数只要乘起来就好了。

总结下步骤：
1，使用tarjan算法求出所有的割点。
2.将割点视作断开，在之后的搜索中视而不见。
3.依次搜索割点断开后的每一个连通块，依照分类讨论，计算答案。

代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int max_n = 550;
int n, m;
int us[max_n];
int vs[max_n];

struct edge{
    int to, next;
}E[max_n * 2];
int head[max_n];
int cnt = 1;
void add(int from, int to) {
    E[cnt].to = to;
    E[cnt].next = head[from];
    head[from] = cnt++;
}
int dfn[max_n], low[max_n];
int tot = 0;
bool is[max_n];
int child;
void tarjan(int u,int fa) {
    dfn[u] = low[u] = ++tot;
    for (int i = head[u];i;i = E[i].next) {
        int v = E[i].to;
        if (v == fa)continue;
        if (!dfn[v]) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                if (u == fa)++child;
                else is[u] = true;
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
}
bool used[max_n];
bool help[max_n];
pii bfs(int st) {
    fill(help, help + n + 10, false);
    int res = 0;
    int cmp = 0;
    used[st] = true;
    queue<int> que;que.push(st);
    while (!que.empty()) {
        int u = que.front();que.pop();
        ++res;
        for (int i = head[u];i;i = E[i].next) {
            int v = E[i].to;
            if (is[v]) {
                if (!help[v]) {
                    ++cmp;
                    help[v] = true;
                }continue;
            }
            if (used[v])continue;
            else {
                used[v] = true;
                que.push(v);
            }
        }
    }return { cmp,res };
}

void init() {
    fill(dfn, dfn + n + 10, false);
    fill(low, low + n + 10, false);
    fill(head, head + n + 10, false);
    fill(dfn, dfn + n + 10, false);
    fill(is, is + n + 10, false);
    fill(used, used + n + 10, false);
    cnt = 1;
}
int main() {
    ios::sync_with_stdio(0);
    int test = 0;
    while ((cin >> m) && m != 0) {
        n = -1;
        for (int i = 1;i <= m;i++) {
            cin >> us[i] >> vs[i];
            n = max(n, us[i]);
            n = max(n, vs[i]);
        }init();
        for (int i = 1;i <= m;i++) {
            add(us[i], vs[i]);
            add(vs[i], us[i]);
        }
        for (int i = 1;i <= n;i++) {
            if (!dfn[i]) {
                child = 0;
                tarjan(i, i);
                if (child >= 2)
                    is[i] = true;
            }
        }
        int ans = 0;ll res = 1;
        for (int i = 1;i <= n;i++) {
            if (is[i])continue;
            else if (!used[i]) {
                pii p = bfs(i);
                if (p.first == 0) {
                    ++ans;++ans;
                    res *= (p.second * (p.second - 1) / 2);
                }
                else if (p.first == 1) {
                    ++ans;
                    res *= p.second;
                }
            }
        }cout << "Case " << ++test << ": " << ans << " " << res << endl;
    }
}