poj 2186 Popular Cows

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

强连通分量

题意:

给一个有向图,问有多少个点,是其他点都可以到达的

其他点都可以到达该点,那么将图转置,就变为该点可以到达其他所有的点

要找这样的点方法有很多,仿照Floyd的DP方法就是最容易写,但是点太多达到10000,会超时

这里用SCC来做

将转置后的图进行缩点,得到一个DAG,这个DAG每个大点内的小点(即原来的点)都是相互可达,关键是看这些大点能不能去到其他大点,如果一个大点能去到其他所有的大点,那么里面的小点也可以

所以就是要找,有多少个大点,可以去到所有其他的大点,可知这样的大点,最多1个!!,而且是入度为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
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
#include <cstdio>
#include <cstring>
#define N 10010
#define M 50010
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

int n,tot;
int dcnt,bcnt,top;
int stack[N];
bool ins[N];
int dfn[N],low[N],belong[N];
int inde[N],outde[N];
int head[N];
struct edge
{
int u,v,next;
}e[M];

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

void tarjan(int u)
{
stack[++top] = u;
ins[u] = true;
dfn[u] = low[u] = ++dcnt;
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%d",&n,&tot);
memset(head,-1,sizeof(head));
for(int i=0; i<tot; i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(v,u,i);
}

memset(dfn,0,sizeof(dfn));
memset(ins,false,sizeof(ins));
dcnt = bcnt = top = 0;
for(int i=1; i<=n; i++)
if(!dfn[i])
tarjan(i);

memset(inde,0,sizeof(inde));
memset(outde,0,sizeof(outde));
for(int i = 0; i<tot; i++)
{
int u = belong[e[i].u];
int v = belong[e[i].v];
if(u != v)
{
++outde[u];
++inde[v];
}
}
int c = 0 , x = 1;
for(int i=1; i<=bcnt; i++)
if(!inde[i])
{
c++;
x = i;
}
if(c != 1) printf("0\n"); //大点只可以有1个
else
{
int c = 0;
for(int i=1; i<=n; i++)
if(belong[i] == x)
c++;
printf("%d\n",c);
}
return 0;
}