poj 1236 Network of Schools

本文从WordPress迁移而来, 查看全部WordPress迁移文章

强连通分量 缩点

题意:这个题意比较难懂,题意读懂了,转化过来也不容易

输入n,表示n个学校(1到n编号),下面n行,分别是对应每个学校的信息。每个学校可以给其他学校共享一些软件接而共享下去,要让所有学校用上软件,需要多少个学校带头共享软件;另外要让每个学校共享的软件都能被其他所有学校用上,那么要在原来的共享计划中,另外加入那些具体的共享呢(例如原来A学校不向B学校共享的,为了达到目的,A学校需要向B学校共享,因而增加了1)

首先建立有向图,A向B共享软件,则有向边A—>B

所有第1个问题,问的就是要多少次才能遍历完整个有向图,因为有这么多的学校带头共享软件了,沿着路径延伸,可以到达他们子树下的所有点,要让所有学校用上软件(不一定用上相同的软件,即软件的来源可以不同),其实就是要到达图中的每个点

做法是,将原图进行缩点,变成一个DAG,在这个DAG中,入度为0的点,就是答案(这个结论不难理解,思考一下即可)

对于第2个问题,一个学校共享软件出来,要让所有其他学校用上,而且所有学校都要做到这点,那么狠显然,就是令整个图变成一个 强连通图 , 那么问题就是,要在原图中,添加多少条边,原图才能变成一个强连通图?

答案是,将原图缩点,变成一个DAG,统计这个DAG入度为0的点的个数和出度为0的点的个数,答案就是两者中的较大值,因为有一个结论,这些边一定是出度为0点指向入度为0的点

(这个结论也不太难理解,但是建议深入思考,最好证明)

那么要实现这个代码,其实是不难的,建图,运行tarjan求强连通分量并且缩点,然后统计缩点后的DAG

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
//将原图缩点为一个DAG
//需要多少次才能遍历完这个DAG,就是看这个DAG有多少个入度为0的点
//往这个DAG添加多少边才能使其成为强连通图,就是找出入度和出度为0的最大值

#include <cstdio>
#include <cstring>
#define N 110
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
int n,tot;
int dcnt,bcnt;
int dfn[N] , low[N] , belong[N];
int stack[N] , top;
bool ins[N];
int inde[N],outde[N];
int head[N];
struct edge
{
int u,v,next;
}e[N*N];

void add(int u ,int v)
{
e[tot].u = u; e[tot].v = v;
e[tot].next = head[u]; head[u] = tot++;
}

void tarjan(int u)
{
dfn[u] = low[u] = ++dcnt;
stack[++top] = u;
ins[u] = true;
for(int k=head[u]; k!=-1; k=e[k].next)
{
int v = e[k].v;
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u] , low[v]);
}
else if(ins[v])
low[u] = min(low[u] , dfn[v]);
}
if(dfn[u] == low[u])
{
++bcnt;
while(1)
{
int x = stack[top--];
ins[x] = false;
belong[x] = bcnt;
if(x == u) break;
}
}
}

int main()
{
scanf("%d",&n);
tot = 0;
memset(head,-1,sizeof(head));
for(int i=1; i<=n; i++)
{
int v;
while(scanf("%d",&v)!=EOF && v)
add(i,v);
}
dcnt = bcnt = top = 0;
memset(dfn,0,sizeof(dfn));
memset(belong,0,sizeof(belong));
memset(ins,false,sizeof(ins));
for(int i=1; i<=n; i++)
if(!dfn[i])
tarjan(i);
if(bcnt == 1)
{
printf("1\n0\n");
return 0;
}
memset(inde,0,sizeof(inde));
memset(outde,0,sizeof(outde));
for(int i=1; i<=n; i++)
for(int k=head[i]; k!=-1; k=e[k].next)
{
int u = belong[i];
int v = belong[e[k].v];
if(u != v)
{
outde[u]++;
inde[v]++;
}
}
int res = 0 , _res = 0;
for(int i=1; i<=bcnt; i++)
{
if(!inde[i]) res++;
if(!outde[i]) _res++;
}
printf("%d\n%d\n",res,max(res , _res));
return 0;
}