在连通图G中,如果删除了某个点u之后,得到的子图不连通,那么点u就被称为关节点。

求关节点可以用dfs来求。

具体就是用到了几个数组

表名意义
dfn[u]节点u的dfs序
p[u]节点u的父节点
low[u](dfn[u]、u的子节点的low值的最小值、u的树枝边的dfn)的最小值

对于无向图来说:

关节点的性质有两条:

  • 存在至少一条树枝边(u, v) low[v]>=dfn[u]
  • 对于根结点需要特别判断,只要有多于一条树枝边则为割点

对于有向图来说:

  • 关节点的low[u]==dfn[u]

把图的关节点及其子树中的点取出,就构成了一个强连通分量。

所以,求强连通分量其实就是在求关节点。

题目:GRL_3_A

这题是求无向图的关节点的题目。代码如下:

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

#define MAXN 100005

vector<int> G[MAXN];
bool vis[MAXN] = {false};
int p[MAXN] = {0};
int low[MAXN] = {0};
int dfn[MAXN] = {0};
int v, e;
int js_dfs = 0;
set<int> ans;

void dfs(int u, int pre)
{
    dfn[u] = low[u] = ++js_dfs;

    vis[u] = true;

    for (int v : G[u])
    {
        if (!vis[v]) //树枝边
        {
            p[v] = u;
            dfs(v, u);
            low[u] = min(low[u], low[v]);
        }
        else if (v != pre) //后向边
        {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int s, t;
    cin >> v >> e;
    for (int i = 0; i < e; ++i)
    {
        cin >> s >> t;
        G[s].push_back(t);
        G[t].push_back(s);
    }

    dfs(0, -1);
    //对dfs树的根节点要特殊处理,出度>2才是关节点
    int np = 0;

    for (int i = 1; i < v; ++i)
    {
        if (p[i] == 0)
            np++;
        else if (dfn[p[i]] <= low[i])//不存在树枝边指向p[i]以上的节点
            ans.insert(p[i]);
    }

    if (np > 1)
        ans.insert(0);

    for (int x : ans)
    {
        cout << x << endl;
    }
}

转载请注明出处:https://www.longjin666.top/?p=764

欢迎关注我的公众号“灯珑”,让我们一起了解更多的事物~

你也可能喜欢

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注