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;
    }
}