「Bzoj 2730」「HNOI2012」矿场搭建 (边双联通分量+分类讨论)

Bzoj 2730
题意：给一张无向图，让你加一些出口，使得任意点删除后图上任意点都能找到出口。

复习一波点双联通分量
考虑求出割点和双联通分量，然后对于每个双联通分量，我们考虑
若这个双联通分量有两个及以上割点，那么不需要建立出口
若这个双联通分量有一个割点，那么如果这个割点删了这个图就找不到出口了，要加一个出口
若这个双联通分量没有割点，即这个子图与其他子图不连通，要加两个出口

加出口即加在任意非割点的点上即可

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<stack>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

int kse = 0;

namespace flyinthesky {

    struct edge {
        int v, nxt;
    } ed[1005];

    int m, n, dfn[505], low[505], sz, dcc_tot, cut[505];
    int hd[505], en, ans2;
    unsigned LL ans;
    stack<int > s;
    vector<int > dcc[505];

    void ins(int u, int v) {ed[++en] = (edge){v, hd[u]}, hd[u] = en;}

    void tarjan(int u, int fa) {
        dfn[u] = low[u] = ++sz, s.push(u);
        if (fa == 0 && hd[u] < 0) {
            s.pop();
            return ;
        }
        int flag = 0;
        for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (e.v == fa) continue ;
            if (!dfn[e.v]) {
                tarjan(e.v, u);
                low[u] = min(low[u], low[e.v]);
                if (low[e.v] >= dfn[u]) {
                    ++flag;
                    if (fa != 0 || flag > 1) cut[u] = 1;
                    int whw;
                    ++dcc_tot;
                    do {
                        whw = s.top(); s.pop();
                        dcc[dcc_tot].push_back(whw);
                    } while (whw != e.v);
                    dcc[dcc_tot].push_back(u);
                }
            } else low[u] = min(low[u], dfn[e.v]);
        }
    }

    void clean() {
        ans = 1ll, ans2 = 0, dcc_tot = 0;
        en = -1, ms(hd, -1), ms(cut, 0);
        sz = n = 0, ms(dfn, 0), ms(low, 0);
        for (int i = 0; i <= 501; ++i) dcc[i].clear();
    }
    int solve() {

        clean();
        for (int x, y, i = 1; i <= m; ++i) {
            scanf("%d%d", &x, &y);
            ins(x, y), ins(y, x);
            n = max(n, max(x, y));
        }

        for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i, 0);

        for (int x = 1; x <= dcc_tot; ++x) {
            unsigned LL tmp = 0, gd = 0;
            for (int i = 0; i < (int)dcc[x].size(); ++i) {
                int u = dcc[x][i];
                if (!cut[u]) ++tmp; else ++gd;
            }
            if (gd == 0) {
                ans2 += 2;
                ans *= (tmp - 1) * tmp / 2;
            } else if (gd == 1) {
                ans *= tmp;
                ++ans2;
            }
        }

        printf("Case %d: %d %llu\n", ++kse, ans2, ans);

        return 0;
    }
}
int main() {
    while (scanf("%d", &flyinthesky::m) == 1 && flyinthesky::m) flyinthesky::solve();
    return 0;
}