题解：B3610 [图论与代数结构 801] 无向图的块
本题求的是点双连通分量。还是先讲一下有关的概念：
割点：在一个无向连通图中，如果删除某个点和这个点关联的所有边，使剩下的图不再连通的点。
点双连通图：在一个无向连通图中，对于任意一个点，若删除这个点和这个点关联的所有边后，剩下的图仍能连通的图。
点双连通分量： 在无向图 $G$ 中，如果一个点双连通子图 $G’$ 不是任何一个点双连通子图的真子集，则图 $G’$ 为图 $G$ 的极大点双连通子图，即点双连通分量。
接下去讲解法（以下用 dfn 数组记录访问每个点的时间，用一个 low(u) 来表示 $u$ 以及其后代最多经过一条反向边能回到的最早的时间戳）。
在一个连通图中，若点 $u$ 为树根，对于点 $u$ ，若当且仅当它有两个或者更多的子结点时，则它为割点；若点 $u$ 为非根的结点，则有定理—在无向连通图 $G$ 的 DFS 树中，$u$ 是个割点当且仅当 $u$ 存在一个子结点 $v$，使得 $v$ 及其所有后代都没有反向边连回 $u$ 的祖先（注意：不包括 $u$）。
则当一条边 $(u,v)$ 有 low[v] >= dfn[u] 时 $u$ 为割点。将 low[u] 更新时，分为树边 low[u] = min (low[u],dfn[u]) 和反向边 low[u] = min (low[u],dfn[v]) 即可。
记录点双连通分量也很简单，首先用栈压入保存元素，等找到割点后再弹出并用 set 记录就行。为什么要用 set？原因很简单，就是它能不重复且有序的记录元素。
最后需要注意一下输出的大小顺序，直接对 set 做一次 sort 即可输出。
代码如下：
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <set>
#include <stack>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 3e5 + 5;
const int MOD = 1e9 + 7;
int n,m,cnt,bcc_cnt,times;
int dfn[MAX],low[MAX],bcc_in[MAX];
int to[MAX << 1],head[MAX << 1],nxt[MAX << 1];
bool vis[MAX];
set <int> bcc[MAX];
stack <pair <int,int> > s;
inline int read ();
void _add (int u,int v);
void dfs (int u,int fa);
int main ()
{
n = read ();m = read ();
for (int i = 1;i <= m;++i)
{
int u = read (),v = read ();
_add (u,v);_add (v,u);
}
for (int i = 1;i <= n;++i)
if (!dfn[i]) dfs (i,-1);
printf ("%d\n",bcc_cnt);
sort (bcc + 1,bcc + 1 + bcc_cnt);
for (int i = 1;i <= bcc_cnt;++i)
{
for (set <int>::iterator it = bcc[i].begin ();it != bcc[i].end ();++it) printf ("%d ",*(it));
puts ("");
}
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
void _add (int u,int v)
{
to[++cnt] = v;
nxt[cnt] = head[u];
head[u] = cnt;
}
void dfs (int u,int fa)
{
dfn[u] = low[u] = ++times;
int child = 0;
for (int i = head[u];i;i = nxt[i])
{
int v = to[i];
if (!dfn[v])
{
s.push ({u,v});
++child;
dfs (v,u);
low[u] = min (low[u],low[v]);
if (low[v] >= dfn[u])
{
++bcc_cnt;
while (1)
{
int x = s.top ().first,y = s.top ().second;
s.pop ();
bcc_in[x] = bcc_in[y] = bcc_cnt;
bcc[bcc_cnt].insert (x);
bcc[bcc_cnt].insert (y);
if (x == u && y == v) break;
}
}
}
else if (dfn[v] < dfn[u] && v != fa)
{
s.push({u,v});
low[u] = min (low[u],dfn[v]);
}
}
}
|
