文章目录
  1. 1. 什么是强连通分量
    1. 1.1. 求强连通分量(强连通分量分解)的算法
      1. 1.1.1. Korasaju
      2. 1.1.2. Tarjan
  2. 2. POJ2762 - Going from u to v or from v to u?
    1. 2.1. 题意
    2. 2.2. 解题思路
      1. 2.2.1. 缩点思路
    3. 2.3. AC代码
  3. 3. POJ 1236 - Network of Schools
    1. 3.1. 题意
    2. 3.2. 解题思路
    3. 3.3. AC代码

引言:今天的专题本来是“2017 SHU 8.15 连通性、割、回路、拓扑排序”,但我只做了拓扑排序和强连通的部分,其他都不会做,连名字都只是听蔡大佬吹B过罢了。G是原题,F题是原题改个邻接表,就不在这写了。


什么是强连通分量

  • 白书上这么讲的:对于一个有向图顶点的子集S,如果在S内任取两个顶点u和v,都能找到一条从u到v的路径,那么就称S是强连通的。

  • 白话文:截取一张连通图的某一部分,发现不管从A到B,还是从B到A,还是从C到Z,还是从哪到哪都走得通,那么这部分就是强连通分量。需要注意的是,单个点也是强连通分量。

    虚线包围的部分构成一个强连通分量

虚线所示为强连通分量(其他单个白圈也自成强连通分量)

求强连通分量(强连通分量分解)的算法

  • 主要是Korasaju和Tarjan两种算法,复杂度都是O(N+M)O(N+M)

    Korasaju

    • 在一张有向连通图中,将所有边反向后,按同样方向走,强连通分量的部分的连通性不受影响,而其他部分必无法走通,所以我们可以用这种方法来求强连通分量。
    • 具体方法:强连通分量分解可以通过两次简单的DFS实现。
      • 第一次DFS时,选取任意定点作为起点,遍历所有尚未访问过的顶点,并在回溯前给顶点标号,这样是为了实现叶子部分的标号最小,越接近根标号越大。对剩余未访问过的顶点,不断重复上述过程。
      • 第二次DFS时,先将所有边反向,然后以标号最大的顶点为起点进行DFS。这样DFS所遍历的顶点集合就构成了一个强连通分量。之后,只要还有尚未访问过的顶点,就从中选取标号最大的顶点不断重复上述过程。

    Tarjan

    不会做。

POJ2762 - Going from u to v or from v to u?

题意

  • 题如其名,就是说一个山洞里面有许许多多的房间,问是否任意两个房间之间可以到达,只需满足u可以到v或者v可以到u即可,并不是且的关系。比如说样例,一共3个房间,1号房间可以走到2号房间,2号房间可以走到3号房间,3号房间可以走到1号房间,很明显这样是可以的。
  • 但实际上这道题并不是裸的强连通,因为它不是且的关系,但是这道题要用到强连通的知识。

解题思路

  • 这道题一眼过去感觉Floyd好像可以,但我没这么尝试,因为它是多组数据,单组数据O(n3)O(n^3)还能说的过去,多组的话数据量一多肯定就炸了。

  • 可以想到拓扑排序,如果删去一个点,出现了多个入度为0的点,那么这些入度为0的点肯定只能通过被删去的点到达,言下之意是,至少这些入度为0的点无法相互到达。想想好像拓扑是可以的,但有个问题就是它能不能进行拓扑排序,拓扑排序的禁忌就是形成环,很显然这道题是可以形成环的,想一想强连通分量就是用来简化有向图的,可以将那些环都化为点。

  • 思路清晰了:用强连通分量分解+缩点将图化为无环图,然后用拓扑排序来确定是否会出现多个入度为0的点的情况(也就是说缩点后的图是不是一个单链)。

  • 网上题解都是Tarjan的做法的,我一下午都迷醉在白书的Korasaju的坑里,白书没有告诉怎么缩点,我简直疯了,又没有别的书可以参考,只好自己想了很久才想出来一种办法进行缩点。最主要是白书都不告诉我这个算法叫做Korasaju,也没有提到Tarjan算法,我怀疑是不是因为白书是日本人编的,而且Korasaju刚好就是个日本人。

    缩点思路

    • 我姑且把一个强连通分量叫做一个集合。前面已经说了,一个点也算强连通分量,因此一个点也算一个集合。
    • 我以一个集合为单位重新构建一张连通图,一个集合中所有点的通向集合外的出边作为集合的出边,出边指向另一个集合。如上图,假设点8、9、10属于集合3,点5、6、7属于集合4,点4属于集合5,点3属于集合6。可以看到集合3中只有9指向7的边指向集合外,我将这条边记为新图的集合3指向集合4的边。同理,集合4有指向集合5,指向集合6的两条边。这个实现通过一次DFS,回溯时遍历该点(属于集合A)的所有出边,如果指向的点和该点不属于同一集合(属于集合B),且集合A指向集合B的边没有记录过,则记集合A指向集合B有一条边。

缩点示意

AC代码

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#define _CRT_SECURE_NO_WARNINGS
#pragma comment (linker,"/STACK:102400000,102400000")
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<ctime>
#include<set>
typedef long long ll;
using namespace std;
#define INF 0x3f3f3f3f
#define MOD (ll)(1e9+7)
inline int read()
{
int a=0, f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)) (a*=10)+=c-'0', c=getchar();
return a*f;
}
vector<int> vec[1010];
vector<int> rvec[1010];
vector<int> vs;
vector<int> g[1010];
int vis[1010];
int cmp[1010];
int in[1010];
int n,m;
void dfs(int v)
{
vis[v]=1;
for(int i=0;i<vec[v].size();i++)
if(!vis[vec[v][i]])dfs(vec[v][i]);
vs.push_back(v);
}
void rdfs(int v,int k)//反过来dfs
{
vis[v]=1;
cmp[v]=k;
for(int i=0;i<rvec[v].size();i++)
if(!vis[rvec[v][i]])rdfs(rvec[v][i],k);
}
void dfs2(int v)//缩点重画集合图
{
vis[v]=1;
for(int i=0;i<vec[v].size();i++)
if(!vis[vec[v][i]])
dfs2(vec[v][i]);
int k=cmp[v];
for(int i=0;i<vec[v].size();i++)
if(cmp[vec[v][i]]!=k)
{
for(int j=0;j<g[k].size();j++)
if(g[k][j]==cmp[vec[v][i]])//判断出边所对的集合是否已加过
goto ctn;
in[cmp[vec[v][i]]]++;//出边所对的集合的入度++
g[k].push_back(cmp[vec[v][i]]);//两个集合相连
ctn:
continue;
}
}
int topo(int cnt)
{
queue<int> q;
int c=0;

for(int i=0;i<cnt;i++)
{
if(!in[i])
{
q.push(i);
c++;
}
}
//printf("|%d,%d|",cnt,c);
if(c>1)
return 0;
while(!q.empty())
{
int tmp=q.front();
q.pop();
c=0;
for(int i=0;i<g[tmp].size();i++)
{
in[g[tmp][i]]--;
if(!in[g[tmp][i]])
{
q.push(g[tmp][i]);
c++;
}
}
//printf("|%d|",c);
if(c>1)
return 0;
}
return 1;
}
void solve()
{
memset(vis,0,sizeof(vis));
vs.clear();
for(int i=1;i<=n;i++)
if(!vis[i])dfs(i);
memset(vis,0,sizeof(vis));
memset(cmp,-1,sizeof(cmp));
for(int i=0;i<n;i++)
g[i].clear();
int cnt=0;
for(int i=vs.size()-1;i>=0;i--)
if(!vis[vs[i]])rdfs(vs[i],cnt++);
memset(vis,0,sizeof(vis));
memset(in,0,sizeof(in));
for(int i=1;i<=n;i++)
if(!vis[i])dfs2(i);
if(topo(cnt))
puts("Yes");
else
puts("No");
//printf("|%d|\n",cnt);
}
int main(void)
{
int T=read();
while(T--)
{
n=read();
m=read();
for(int i=1;i<=n;i++)
{
vec[i].clear();
rvec[i].clear();
}
for(int i=0;i<m;i++)
{
int u=read(),v=read();
vec[u].push_back(v);
rvec[v].push_back(u);
}
solve();
}
return 0;
}

POJ 1236 - Network of Schools

  • 这道题是一个很棒的强连通题!(流口水)

题意

  • N(2<N<100)各学校之间有单向的网络,每个学校得到一套软件后,可以通过单向网络向周边的学校传输,问题1:初始至少需要向多少个学校发放软件,使得网络内所有的学校最终都能得到软件。2,至少需要添加几条传输线路(边),使任意向一个学校发放软件后,经过若干次传送,网络内所有的学校最终都能得到软件。

  • 也就是给定一个有向图,求:

    Subtask A: 至少要选几个顶点,才能做到从这些顶点出发,可以到达全部顶点

    Subtask B: 至少要加多少条边,才能使得从任何一个顶点出发,都能到达全部顶点

解题思路

  • 子任务1和POJ2762,也就是上一道题有共通点。我们从上道题可以获知缩点后,入度为0的点无法从现存的任何点到达,因此每一个缩点后入度为0的点我们都需要选择在内。至于是否从入度为0的点可以走完所有点,这个我不知道,懒得证明了,画两下觉得对就行了……
  • 子任务2是要让整个图变成一个全连通图,也就是只有一个全连通分量。全连通分量的性质就是没有入度为0的点,也没有出度为0的点。也就是说,我们要加几条边才能消灭入度为0(设有m个)和出度为0的点(设有n个)。很显然需要max(m,n)条边,因为我最经济的打算是加一条边,把入度为0的点和出度为0的点连起来,就能同时消去一个入度为0的点和一个出度为0的点,但天下不一定总能有这么好的算盘,当m和n不等时,就只能一个一个消了,因此是max(m,n)个。注意有一个坑点,当一开始就是强连通时需要特判输出1和0。
  • 对了,有一篇文章我觉得很有意思:强连通分量及缩点tarjan算法解析

AC代码

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#define _CRT_SECURE_NO_WARNINGS
#pragma comment (linker,"/STACK:102400000,102400000")
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<ctime>
#include<set>
typedef long long ll;
using namespace std;
#define INF 0x3f3f3f3f
#define MOD (ll)(1e9+7)
inline int read()
{
int a=0, f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)) (a*=10)+=c-'0', c=getchar();
return a*f;
}
vector<int> vec[105];
vector<int> rvec[105];
bool vis[105];
vector<int> vs;
vector<int> g[105];
int cmp[105];
int in[105];
int N;
void dfs(int v)
{
vis[v]=1;
for(int i=0;i<vec[v].size();i++)
if(!vis[vec[v][i]])dfs(vec[v][i]);
vs.push_back(v);
}
void rdfs(int v,int k)
{
vis[v]=1;
cmp[v]=k;
for(int i=0;i<rvec[v].size();i++)
if(!vis[rvec[v][i]])rdfs(rvec[v][i],k);
}
void dfs2(int v)
{
vis[v]=1;
for(int i=0;i<vec[v].size();i++)
if(!vis[vec[v][i]])dfs2(vec[v][i]);
int k=cmp[v];
for(int i=0;i<vec[v].size();i++)
{
if(k!=cmp[vec[v][i]])
{
for(int j=0;j<g[k].size();j++)
if(g[k][j]==cmp[vec[v][i]])
goto ctn;
in[cmp[vec[v][i]]]++;
g[k].push_back(cmp[vec[v][i]]);
//printf("`%d->%d`\n",v,vec[v][i]);
}
ctn:
continue;
}
}
void solve()
{
memset(vis,0,sizeof(vis));
memset(cmp,-1,sizeof(cmp));
vs.clear();
for(int i=1;i<=N;i++)
if(!vis[i])dfs(i);
//puts("A");
memset(vis,0,sizeof(vis));
int cnt=0;
for(int i=vs.size()-1;i>=0;i--)
if(!vis[vs[i]])rdfs(vs[i],cnt++);
//puts("B");
memset(in,0,sizeof(in));
memset(vis,0,sizeof(vis));
for(int i=0;i<=N;i++)
g[i].clear();
for(int i=1;i<=N;i++)
if(!vis[i])dfs2(i);
//puts("C");
int ansin=0,ansout=0;
for(int i=0;i<cnt;i++)
{
if(!in[i])ansin++;
if(!g[i].size())ansout++;
}

printf("%d\n%d\n",ansin,cnt>1?max(ansin,ansout):0);

}
int main(void)
{
while(scanf("%d",&N)==1)
{
for(int i=0;i<=N;i++)
{
vec[i].clear();
rvec[i].clear();
}
for(int i=1;i<=N;i++)
{
for(int u=1;;u++)
{
int v=read();
if(!v)
break;

vec[i].push_back(v);
rvec[v].push_back(i);
}

}
solve();
}
return 0;
}
文章目录
  1. 1. 什么是强连通分量
    1. 1.1. 求强连通分量(强连通分量分解)的算法
      1. 1.1.1. Korasaju
      2. 1.1.2. Tarjan
  2. 2. POJ2762 - Going from u to v or from v to u?
    1. 2.1. 题意
    2. 2.2. 解题思路
      1. 2.2.1. 缩点思路
    3. 2.3. AC代码
  3. 3. POJ 1236 - Network of Schools
    1. 3.1. 题意
    2. 3.2. 解题思路
    3. 3.3. AC代码