poj 2553 The Bottom of a Graph

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

连通分量简单题

题意:给出一个有向图,找出一个点集,里面要么是一个点,要么多于一个点,当多于一个点,点集内任意两个点都必须互达,注意,如果一个点可达另一个点,但反过来不成立的话,它们不能共存于一个点集里。输出这个点集

强连通分量缩点后,一个大点内的点都满足相互可达的条件。缩点后得到一个DAG,无环,那么任何出度不为0的大点都不能选,因为有了出度就会指向其他点,但是其他点是指不回来的(否则有环矛盾),所以只能找出度为0的点,将这些出度为0的大点里面的小点全部输出即可

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 5100
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back

int n;
vector<int>e[N];
int dfn[N],low[N],belong[N],stack[N],outde[N],dcnt,bcnt,top;
bool ins[N];

void tarjan(int u){
dfn[u] = low[u] = ++dcnt;
stack[++top] = u; ins[u] = true;
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
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(true){
int x = stack[top--];
belong[x] = bcnt; ins[x] = false;
if(x == u) break;
}
}
}

void scc(){
cl(dfn,0);
cl(ins,false);
cl(outde,0);
dcnt = bcnt = top = 0;
for(int i = 1; i <= n; i++)
if(!dfn[i])
tarjan(i);
for(int i = 1; i <= n; i++)
for(int j = 0; j < e[i].size(); j++){
int u = belong[i];
int v = belong[e[i][j]];
if(u != v) outde[u]++;
}
for(int i = 1; i <= n; i++)
if(outde[belong[i]] == 0)
printf("%d ",i);
printf("\n");
}

int main(){
int m;
while(scanf("%d%d",&n,&m)!=EOF){
for(int i = 0; i <= n; i++)
e[i].clear();
for(int i = 0; i < m; i++){
int u,v;
scanf("%d%d",&u,&v);
e[u].pb(v);
}
scc();
}
return 0;
}