题意#

这题给我们一个图，求这一个图的割点。

首先我们需要了解割点是什么，简单来说就是删除了这个点之后整个图不是连通图。

比如下图中的 $②$ 就是割点*（图片来自OI Wiki）*。

方法#

OI Wiki上对割点的讲解：link.

首先用dfs序给每一个节点打上时间戳*（图片来自OI Wiki）*，存在dfn[]数组中：

我们用像求强连通分量一样的 Tarjan 算法遍历每一个节点，用low[]数组存储从这个节点出发能到达的最远古的节点。

我们遍历每一个节点，然后更新节点的low[]值。更新方法：

如果搜索到的下一个节点没有在队列中，搜索完这下一个节点之后，如果这个儿子的low[]值小于自己的low[]值，就将low[]的值更新为它的儿子的low[]值。

本文中程序的v为当前节点，u为循环到的节点。

1
      tarjan(u, v);                   //找下面这个点
2
      low[v] = min(low[v], low[u]);   //这个点low[v]的值就是当前low[]的值与找到的u点的low[]值的最小值

还有可能搜到了还在队列中的节点（即自己的祖先），就取low[v]与num[u]的最小值。

1
else low[v] = min(low[v], num[u]);   //low[v]就取这个点的low值与循环到的点u的dfn[u]的最小值

接下来就要考虑如何发现割点并把发现的割点的数量记录下来。

当找到的点不在队列中时，先更新low[]的值，再判断如果low[u] >= num[v]，即这个点不能回到祖先节点了，

并且此时所在的点不是祖先节点，而且此时所在的点没有被标记过，就 flag[v] = true, res++。

1
      if (father != v && low[u] >= num[v] && !flag[v]) flag[v] = true, res++; //如果满足割点的条件就标记是割点，并且让答案的个数增加。

另外，如果此时所在的点是祖先节点，并且它有两个及以上的儿子 （只有不在队列中的点才算儿子），而且没被标记过，就 flag[v] = true, res++。

1
  if (father == v && child >= 2 && !flag[v])    //如果自己有两个儿子并且没有被访问过
2
                                                //只有不在队列中的点才算儿子。
3
    flag[v] = true, res++;

上面的儿子可以在遍历每一个节点的时候累加。

代码#

1
#include <cstdio>
2
#include <vector>
3
#include <iostream>
4
using namespace std;
5

6
inline int read() {
7
  int X = 0; bool flag = 1; char ch = getchar();
8
  while (ch < '0' || ch > '9') {if (ch == '-') flag = 0; ch = getchar();}
9
  while (ch >= '0' && ch <= '9') {X = (X << 1) + (X << 3) + ch - '0'; ch = getchar();}
10
  if (flag) return X;
11
  return ~ (X - 1);
12
}
13

14
inline void write(int X) {
15
  if (X < 0) {putchar('-'); X = ~ (X - 1);}
16
  int s[50], top = 0;
17
  while (X) {s[++top] = X % 10; X /= 10;}
18
  if (!top) s[++top] = 0;
19
  while (top) putchar(s[top--] + '0');
20
  putchar(' ');
21
  return;
22
}
23

24
int head[20004], low[20004], num[20004];
25
int index, res, cnt;
26
bool flag[20004], vis[20004];
27

28
vector<int> edge[100001];
29

30
void tarjan(int v, int father) {      //Tarjan算法
31
  num[v] = low[v] = ++index;          //标记dfn[]访问顺序，还有low[]的初始值
32
  vis[v] = true;                      //标记这个点被访问过
33
  int child = 0;
34
  for (auto u : edge[v]) {
35
    if (!vis[u]) {                    //如果u没有被访问过
36
      child++;
37
      tarjan(u, v);                   //找下面这个点
38
      low[v] = min(low[v], low[u]);   //这个点low[v]的值就是当前low[]的值与找到的u点的low[]值的最小值
39
      if (father != v && low[u] >= num[v] && !flag[v]) flag[v] = true, res++; //如果满足割点的条件就标记是割点，并且让答案的个数增加。
40
    } else low[v] = min(low[v], num[u]);        //low[v]就取这个点的low值与循环到的点u的dfn[u]的最小值
41
  }
42
  if (father == v && child >= 2 && !flag[v])    //如果自己有两个儿子并且没有被访问过
43
                                                //只有不在队列中的点才算儿子。
44
    flag[v] = true, res++;
45
}
46

47
int main() {
48
  int n, m;
49
  n = read(); m = read();
50
  for (int i = 1; i <= m; i++) {
51
    int x, y;
52
    x = read(); y = read();
53
    edge[x].push_back(y);
54
    edge[y].push_back(x);
55
  }
56
  for (int i = 1; i <= n; i++)
57
    if (!vis[i]) index = 0, tarjan(i, i);
58
  write(res);
59
  putchar('\n');
60
  for (int i = 1; i <= n; i++) if (flag[i]) write(i);
61
  putchar('\n');
62
  return 0;
63
}