「POJ-1523」SPF-割点

Consider the two networks shown below. Assuming that data moves around these networks only between directly connected nodes on a peer-to-peer basis, a failure of a single node, $3$, in the network on the left would prevent some of the still available nodes from communicating with each other. Nodes $1$ and $2$ could still communicate with each other as could nodes $4$ and $5$, but communication between any other pairs of nodes would no longer be possible.

Node $3$ is therefore a Single Point of Failure (SPF) for this network. Strictly, an SPF will be defined as any node that, if unavailable, would prevent at least one pair of available nodes from being able to communicate on what was previously a fully connected network. Note that the network on the right has no such node; there is no SPF in the network. At least two machines must fail before there are any pairs of available nodes which cannot communicate.

链接

POJ-1523

题解

构建一棵 $dfs$ 树，序列 $dfn[i]$ 为深度优先数，表示 $dfs$ 时访问 $i$ 节点的序号，$low[i]$ 表示从 $i$ 节点出发能访问到的最小的深度优先数。

当且仅当节点 $u$ 满足如下两个条件之一时，$u$ 为割点：

$u$ 为 $dfs$ 树的根，且 $u$ 至少有两个子节点。
$u$ 不是 $dfs$ 树的根，至少存在一个节点 $v$ 是 $u$ 的子节点，且 $low[v] >= dfn[u]$。

若 $u$ 为割点，记 $subnets[u]$ 为 $u$ 的子节点数，则去掉 $u$ 后，图被分成 $subnets[u] + 1$ 个部分（每个子节点的部分和 $u$ 的祖先的部分），若 $u$ 为 $dfs$ 树的根，则分成 $subnets[u]$ 个部分（根节点没有祖先）。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<cstdlib>
#include<map>
#include<set>
const int MAXN = 1005;
std::vector <int> edge[MAXN];
bool vis[MAXN];
int n, idx, son, dfn[MAXN], low[MAXN], cut[MAXN];
inline void tarjan(const int u) {
    dfn[u] = low[u] = ++idx;
    for (int i = 0; i < edge[u].size(); i++) {
        register int v = edge[u][i];
        if (!vis[v]) {
            vis[v] = 1, tarjan(v), low[u] = std::min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                if (u != 1) cut[u]++;
                if (u == 1) son++;
            }
        }
        else low[u] = std::min(low[u], dfn[v]);
    }
}
inline void init() {
    idx = 0, son = 0, memset(vis, 0, sizeof(vis)), vis[1] = 1, memset(cut, 0, sizeof(cut));
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
#endif
    register int u, v, flag, cas = 1;
    while (~scanf("%d", &u)) {
        if (!u) break;
        init();
        memset(edge, 0, sizeof(edge));
        n = 0, scanf("%d", &v), edge[u].push_back(v), edge[v].push_back(u), n = std::max(u, v);
        while (~scanf("%d", &u)) {
            if (!u) break;
            scanf("%d", &v);
            n = std::max(n, std::max(u, v));
            edge[u].push_back(v), edge[v].push_back(u);
        }
        if (cas != 1) printf("\n");
        printf("Network #%d\n", cas++);
        tarjan(1);
        if (son > 1) cut[1]  = son - 1;
        bool valid = 0;
        for (register int i = 1; i <= n; i++)
            if (cut[i])
                valid = 1, printf("  SPF node %d leaves %d subnets\n", i, cut[i] + 1);
        if (!valid) printf("  No SPF nodes\n");
    }
    return 0;
}