POJ1144 Network 题解点双连通分量（求割点数量）

题目大意：给以一个无向图，求割点数量。

这道题目的输入和我们一般见到的不太一样。

它首先输入 \(N\)（\(\lt 100\)）表示点的数量（\(N=0\)表示文件输入结束）。

然后接下来每行输入一组数字。

如果这一组数字只包含一个 \(0\) ，说明本组测试数据输入结束；
否则，假设这些数可以拆分成 \(a_1,a_2,a_3, \cdots ,a_m\)，则说明 \(a_1\) 这个点到 \(a_2,a_3, \cdots , a_m\) 之间都存在着一条边。

所以这道题目想要表达的意思还是一样的 \(\Rightarrow\) 求割点的数量，只不过输入方式和我们平时见到的不太一样。

观察DFS搜索树，我们可以发现有两类节点可以成为割点：

对根节点 \(u\) ，若其有两棵或两棵以上的子树，则该根结点 \(u\) 为割点；
对非叶子节点 \(u\) （非根节点），若其子树的节点均没有指向 \(u\) 的祖先节点的回边，说明删除 \(u\) 之后，根结点与 \(u\) 的子树的节点不再连通，有 \(low[v] \ge dfn[u]\) ；则节点 \(u\) 为割点。

实现代码如下：

#include <iostream>

#include <string>

#include <sstream>

#include <vector>

#include <cstdio>

using namespace std;

const int maxn = 10010;

int n, m, dfn[maxn], low[maxn], f[maxn], cnt, ans;

bool vis[maxn];

vector<int> g[maxn];

void init() {

    ans = cnt = 0;

    for (int i = 1; i <= n; i ++) {

        low[i] = dfn[i] = f[i] = vis[i] = 0;

        g[i].clear();

    }

}

void tarjan(int u) {

    low[u] = dfn[u] = ++cnt;

    int son_num = 0;    // 记录子树数量

    int sz = g[u].size();

    for (int i = 0; i < sz; i ++) {

        int v = g[u][i];

        if (!dfn[v]) {  // v未被访问，(u,v)为树边

            son_num ++;

            f[v] = u;

            tarjan(v);

            low[u] = min(low[u], low[v]);

            if (dfn[u] == 1 && son_num > 1 && !vis[u]) {    // 根节点，子树数量大于1即为割点

                vis[u] = true;

                ans ++;

            }

            else if (dfn[u] != 1 && low[v] >= dfn[u] && !vis[u]) {  // 其余节点子树可追溯到最早的祖先节点要么为v要么为u

                vis[u] = true;

                ans ++;

            }

        }

        else if (f[v] != u) {   // 节点v已被访问，则(u,v)为回边

            low[u] = min(low[u], dfn[v]);

        }

    }

}

int main() {

    while (~scanf("%d", &n) && n) {

        init();

        getchar();

        string s;

        int a, b;

        while (getline(cin, s)) {

            stringstream ss(s);

            ss >> a;

            if (!a) break;

            while ((ss >> b) && b) {

                g[a].push_back(b);

                g[b].push_back(a);

            }

        }

        tarjan(1);

        cout << ans << endl;

    }

    return 0;

}

参考链接：

https://www.cnblogs.com/zjl192628928/p/10467126.html

巴特西

POJ1144 Network 题解点双连通分量（求割点数量）

最新文章

热门文章

巴特西

POJ1144 Network 题解 点双连通分量（求割点数量）

最新文章

热门文章

POJ1144 Network 题解点双连通分量（求割点数量）