UVA 1108: Mining Your Own Business —— 点双连通分量

传送门

题目大意:

给你一张无向连通图,要你设置一些逃生点,使得无向图上任意一个节点崩塌后,其他点都能到一个安全点逃生。问最少需要几个安全点,以及是的安全点最少的方案有多少种。

输入格式:

多组测试数据。

对于每一组测试数据,第一行一个整数 $n$ ,代表边数量, $n=0$ 时,输入结束。

接下来 $n$ 行,每一行两个整数 $s,t$ ,代表 $s$ 到 $t$ 有一条无向边。保证节点编号从 $1$ 开始,并且连续。

输出格式:

对于每组测试数据,输出两个整数,第一个整数代表最小的安全点数,第二个整数代表方案数。格式与样例一致。

测试样例:

Input
9
1 3
4 1
3 5
1 2
2 6
1 5
6 3
1 6
3 2
6
1 2
1 3
2 4
2 5
3 6
3 7
0
Output
Case 1: 2 4
Case 2: 4 1

分析:

我们首先得找到所有的割点,并且求出所有的双连通分量

对于只有一个割点的双连通分量,我们必须要在这个双联通分量里设置一个逃生点,否则如果割点塌陷掉,这个分量里的人就只有等死。

对于有两个及以上割点的双连通分量,我们根本不用管它,因为就算是一个割点塌陷了,也可以从另外的割点逃生。

最后要考虑一种特殊情况:如果整个图就是一个双连通分量,那么我们就必须要设置两个安全点,因为任意一个节点都可能崩塌。

求方案数是简单的乘法原理。

这里简单说一下求割顶双连通分量

割顶:

在无向连通图 G 中:

  1. 根节点 $u$ 为割顶,当且仅当 $u$ 有两个及以上子节点。
  2. 非根节点 $u$ 为割顶,当且仅当 $u$ 的子树中所有节点,都没有边可以连回 $u$ 的祖先( $u$ 的祖先不包括 $u$ )。

我们用 $dfn[]$ 存时间戳, $low[]$ 存从反向边可以到达的时间戳最小的节点。那么对于非根节点 $u$ , $u$ 为割顶的条件即为 low[v] >= dfn[u]

多说一句,如果求,只需把条件改为 low[v] > dfn[u]

双连通分量:

双连通分量分为点双边双。这里重点说点双。

对于一个连通图,如果任意两点存在两条及以上点不重复的路径,则称这个图点双连通。

求解点双的方法与求解割顶息息相关。我们维护一个来保存遍历过的边。注意栈里面存的是边不是点。我比较推荐用 pair<int, int> 来存边。当然用结构体也没问题。

当我们找到一个点 $u$ ,并且 dfs 确定它是割顶之后我们开始出栈,在从栈里拿出当前边 $(u,v)$ 后停止出栈。刚才出栈的所有边的两个端点属于同一个点双连通分量,可以用 $bccno_i$ 保存点 $i$ 的双连通分量编号。注意割顶的双连通分量编号没有意义,因为割顶同时属于多个双连通分量。

推荐用 vector 保存每个双连通分量里的点。

至于边双,我们只需要找出所有桥,桥不属于任何双连通分量,我们排除桥再进行 dfs 找到边双。

求双连通分量的方法与强连通分量很像,因为它们都是 Tarjan 大爷想出的算法。

膜拜 Tarjan 大爷。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

template<class _T> inline void read(_T &_x) {
  int _t, _flag = 0;
  while ((_t = getchar()) != '-' && (_t < '0' || _t > '9'));
  if (_t == '-')  _t = getchar(), _flag = 1;
  _x = _t - '0';
  while ((_t = getchar()) >= '0' && _t <= '9')
    _x = _x * 10 + _t - '0';
  if (_flag)  _x = -_x;
}

typedef long long ll;
typedef pair<int, int> pii;

const int MAX_N = 1e5 + 100;
struct Edge {
  int v, next;
} edge[MAX_N << 1];
ll ans1, ans2;
int head[MAX_N], kk = 1, idx = 0, n, m, mx, cnt_bcc, dfn[MAX_N], low[MAX_N], iscut[MAX_N], bccno[MAX_N];
vector<int> Bcc[MAX_N];
stack<pii> s;

inline void addedge(int u, int v) {
  edge[kk] = (Edge) {v, head[u]}, head[u] = kk++;
}

void init() {
  memset(head, 0, sizeof(head));
  memset(dfn, 0, sizeof(dfn));
  memset(low, 0, sizeof(low));
  memset(iscut, 0, sizeof(iscut));
  memset(bccno, 0, sizeof(bccno));
  idx = cnt_bcc = mx = 0, kk = 1;
  while (!s.empty())
    s.pop();
}

int dfs(int u, int fa) {
  int lowu = dfn[u] = ++idx;
  int child = 0;
  for (int i = head[u]; i; i = edge[i].next)  {
    int v = edge[i].v;
    if (v == fa)  continue;
    pii e = make_pair(u, v);
    if (!dfn[v]) {
      s.push(e);
      ++child;
      int lowv = dfs(v, u);
      lowu = min(lowu, lowv);
      if (lowv >= dfn[u]) {
        iscut[u] = 1;
        ++cnt_bcc;
        Bcc[cnt_bcc].clear();
        while (true) {
          pii x = s.top();
          s.pop();
          if (bccno[x.first] != cnt_bcc) {
            Bcc[cnt_bcc].push_back(x.first);
            bccno[x.first] = cnt_bcc;
          }
          if (bccno[x.second] != cnt_bcc) {
            Bcc[cnt_bcc].push_back(x.second);
            bccno[x.second] = cnt_bcc;
          }
          if (x.first == u && x.second == v)  break;
        }
      }
    }
    else if (dfn[v] < dfn[u] && v != fa) {
      s.push(e);
      lowu = min(lowu, dfn[v]);
    }
  }
  if (fa < 0 && child == 1) iscut[u] = 0;
  return lowu;
}

void solve() {
  ans1 = 0, ans2 = 1;
  if (cnt_bcc == 1) {
    ans1 = 2;
    ans2 = (ll) Bcc[1].size() * (Bcc[1].size() - 1) / 2;
    return;
  }
  for (int i = 1; i <= cnt_bcc; ++i) {
    int cnt_cut = 0;
    for (int j = 0; j < Bcc[i].size(); ++j) {
      int t = Bcc[i][j];
      if (iscut[t])  ++cnt_cut;
    }
    if (cnt_cut == 1) ++ans1, ans2 *= (ll) (Bcc[i].size() - 1);
  }
}

int main() {
  read(n);
  int kase = 0;
  while (n) {
    init();
    for (int i = 1; i <= n; ++i) {
      int a, b;
      read(a), read(b);
      addedge(a, b), addedge(b, a);
      mx = max(mx, a), mx = max(mx, b);
    }
    for (int i = 1; i <= mx; ++i) {
        if (!dfn[i])  dfs(1, -1);
    }
    solve();
    printf("Case %d: %lld %lld\n", ++kase, ans1, ans2);
    read(n);
  }
  return 0;
}