Day21

Day21

今天讲的是强连通量
中间插入了一场比赛
补题

简介

有向图强连通分量:在有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。有向图的极大强连通子图,称为强连通分量(strongly connected components)。

比赛链接
题解

Equivalent Sets

Description:
To prove two sets A and B are equivalent, we can first prove A is a subset of B, and then prove B is a subset of A, so finally we got that these two sets are equivalent.
You are to prove N sets are equivalent, using the method above: in each step you can prove a set X is a subset of another set Y, and there are also some sets that are already proven to be subsets of some other sets.
Now you want to know the minimum steps needed to get the problem proved.
Input
The input file contains multiple test cases, in each case, the first line contains two integers N <= 20000 and M <= 50000.
Next M lines, each line contains two integers X, Y, means set X in a subset of set Y.
Output
For each case, output a single integer: the minimum steps needed.

1
2
3
4
5
6
7
8
9
10
11
Sample Input
4 0
3 2
1 2
1 3
Sample Output
4
2

Hint
Case 2: First prove set 2 is a subset of set 1 and then prove set 3 is a subset of set 1.

题解:对于这样一个题目,很容易就可以把子集关系转换成有向图的一条有向边,那么题目就转换为求最少增加多少条有向边使得该图成为一个强连通图.对于一个图来说,他内部可能存在许多强连通分量,对于这些强连通分量之间,他们是不需要再进行建边了,我们可以将一个个强连通分量缩成一个个点,那么我们只需要让这些缩点后的图(有向无环图)是一个强连通图即可.
这里用到一点贪心的思想:对于一个有向无环图,若有zin个入度为0的点,我们最多只需要增加zin条有向边,若是有zout个出度为0的点,我只需要增加zout条有向边,那么对于一个有向无环图要成为一个强连通图,我们最少只需要增加max(zin,zout)条有向边即可.
code:

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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
using namespace std;
#define ll long long
const int maxn = 20005;
struct Tarjan {
int n; //点的个数

vector<int>e[maxn]; //邻接表存图
int DFN[maxn], LOW[maxn];
int index; //编辑计数器

int stk[maxn]; //栈
bool ins[maxn]; //记录点是否在栈中
int top;

vector<vector<int> >ans;
void init(int N) { //初始化
n = N;

ans.clear();
for (int i = 1; i <= n; i++)
e[i].clear();
top = 0;
index = 0;

memset(DFN, -1, sizeof(DFN));
memset(ins, 0, sizeof(ins));
}

void add_edge(int u, int v) {//添加边
e[u].push_back(v);
}

void dfs(int u) { //从u点开始搜索
DFN[u] = LOW[u] = ++index;
stk[top++] = u; //为了记录这个连通分量中的节点
ins[u] = true;

for (int i = 0; i < e[u].size(); i++) {
int v = e[u][i];
if (DFN[v] == -1) {
dfs(v);
LOW[u] = min(LOW[u], LOW[v]);
}
else if (ins[v])
LOW[u] = min(LOW[u], DFN[v]);
}

if (DFN[u] == LOW[u]) { //当DFN==LOW时说明stk中点可以形成一个强连通分量
vector<int>q;
int v = stk[top - 1];

while (u != v) {
q.push_back(v);
ins[v] = false;
top--;
v = stk[top - 1];
}
q.push_back(u);
ins[u] = false;
top--;

ans.push_back(q);
}
}

void solve() { //运行该函数后产生答案
for (int i = 1; i <= n; i++)
if (DFN[i] == -1) dfs(i);
}
}T;
int num[maxn];
bool vis[maxn];
vector<int> e[maxn]; //存强连通缩点后的得到的新图
int n, m;
int main(){
while (~scanf("%d%d",&n,&m)){
int u, v;
T.init(n); //初始化
while(m--){ //建有向图
scanf("%d%d", &u, &v);
T.add_edge(v, u); //这里是u->v
}
T.solve(); //获得该有向图的所有强连通分量

for (int i = 1; i<=n; i++) //清空新图
e[i].clear();
//缩点
for (int i = 0; i< T.ans.size(); i++)
for (int j = 0; j< T.ans[i].size(); j++)
num[T.ans[i][j]] = i + 1;

/*
for(int i=1;i<=n;i++) //输出缩点情况
printf("%d:%d\n",i,num[i]);
*/

for (int i = 1; i<=n; i++) //建新有向无环图
for (int j = 0; j < T.e[i].size(); j++) {
if (num[i] == num[T.e[i][j]]) continue;
e[num[i]].push_back(num[T.e[i][j]]);
//printf("%d->%d\n",num[i],num[T.e[i][j]]);输出图
}
n = T.ans.size(); //新图的点数

//以上为Tarjan算法的强连通缩点操作,得到新的有向无环图为e[],点数为n

memset(vis, 0, sizeof(vis));
int zin = 0, zout = 0; //分别为入度为0的点数和出度为0的点数
for (int i = 1; i <= n; i++){
if (e[i].size() == 0)zout++;
for (int j = 0; j < e[i].size(); j++)
vis[e[i][j]] = true;
}
for(int i=1;i<=n;i++)
if (!vis[i])zin++;
if (n != 1)printf("%d\n", max(zin, zout));
else printf("0\n"); //若是只有一点点需要特判结果为0,否则输出1
}
return 0;
}

---------------- The End ----------------
0%