铁丝网

互相联通的梦境

0%

tarjan求割点

发表于

这个写起来和tarjan求强连通分量十分相似，也是利用dfs的方式来求出割点。

割点的定义：

如果去掉一个点会使得一个强连通分量成为两个或多个强连通分量，则这个点是割点。

求法：

分成两种情况：

  • 如果是根的话，子树超过一个就是个割点。
  • 如果不是根，而且没有子节点的low值超过这个点的dfn，也就是说没有哪个子节点可以够道它上面的点，那么也是一个割点。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 100005*4;
int n,m;
struct edge
{
   int v,next;
}e[N];
int cnt = 0, front[N], dfn[N], low[N];
bool cut[N];
int t = 0;
void AddEdge(int u,int v)
{
     e[++cnt].v = v;
     e[cnt].next = front[u];
     front[u] = cnt;
}
void tarjan(int xx,int fx)
{
     int rc = 0;
     dfn[xx] = low[xx] = ++t;
     for (int i = front[xx]; i; i = e[i].next)
     {
         int v = e[i].v;
         if(!dfn[v])
         {
             tarjan(v,fx);
             low[xx] = min(low[xx],low[v]);
             if (low[v] >= dfn[xx] && xx != fx) cut[xx] = true;
             if (xx == fx) rc++;
         }
         low[xx] = min(low[xx],dfn[v]);
     }
     if(rc >= 2 && xx == fx) cut[fx] = true;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= m; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        AddEdge(a,b);
        AddEdge(b,a);
    }
    for (int i = 1; i <= n; i++)
    {
        if(!dfn[i]) tarjan(i, i);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if(cut[i]) ans++;
    }
    printf("%d\n",ans);
    for (int i = 1; i <= n; i++)
    {
        if(cut[i]) printf("%d ",i);
    }
    return 0;
}

模版传送门