以前做过poj的一个判断图是否为弱连通的题，然后，这个题和poj那个差不多。
先强连通缩点，然后重新构图，然后找出包含点数最多的 链 ，统计个数即可，可以用拓扑排序搞~
pS：重新构图时有重边，然后导致统计方案数的重复。。wa了好久。。还是wzc神犇告诉我这个蒟蒻的。。
View Code
1
#include <iostream>
2
#include <cstdio>
3
#include <cstdlib>
4
#include <cstring>
5
#include <algorithm>
6
7
#define
N 200000
8
#define
M 5000000
9
#define
BUG system("pause")
10
11
using
namespace
std;
12
13
int
head[N],to[M],next[M];
14
int
dfn[N],low[N];
15
int
st[M],ed[M];
16
int
n,m,cnt,ans,ansnum,mod;
17
int
divg,belong[N],t,p,stk[N],val[N];
18
bool
fg[N];
19
int
num[N],
in
[N],dp[N],q[M],vis[N];
20
21
inline
void
add(
int
u,
int
v)
22
{
23
to[cnt]=v; next[cnt]=head[u]; head[u]=cnt++
;
24
}
25
26
inline
void
read()
27
{
28
memset(head,-
1
,
sizeof
head); cnt=
0
;
29
scanf(
"
%d%d%d
"
,&n,&m,&
mod);
30
for
(
int
i=
1
;i<=m;i++
)
31
{
32
scanf(
"
%d%d
"
,&st[i],&
ed[i]);
33
add(st[i],ed[i]);
34
}
35
}
36
37
inline
void
dfs(
int
u)
38
{
39
low[u]=dfn[u]=++
t;
40
stk[++p]=u; fg[u]=
true
;
41
for
(
int
i=head[u];~i;i=
next[i])
42
{
43
if
(!
dfn[to[i]])
44
{
45
dfs(to[i]);
46
low[u]=
min(low[u],low[to[i]]);
47
}
48
else
if
(fg[to[i]]) low[u]=
min(low[u],dfn[to[i]]);
49
}
50
if
(dfn[u]==
low[u])
51
{
52
divg++
;
53
int
tmp=-
1
;
54
while
(tmp!=
u)
55
{
56
tmp=stk[p--
];
57
belong[tmp]=
divg;
58
val[divg]++
;
59
fg[tmp]=
false
;
60
}
61
}
62
}
63
64
inline
void
topsort()
65
{
66
int
h=
1
,t=
1
,u;
67
for
(
int
i=
1
;i<=divg;i++
)
68
if
(
in
[i]==
0
)
69
{
70
q[t++]=
i;
71
dp[i]=
val[i];
72
num[i]=
1
;
73
}
74
while
(h<
t)
75
{
76
u=q[h++
];
77
for
(
int
i=head[u];~i;i=
next[i])
78
{
79
in
[to[i]]--
;
80
if
(
in
[to[i]]==
0
) q[t++]=
to[i];
81
if
(vis[to[i]]==u)
continue
;
//
有重边!!
82
if
(dp[to[i]]<dp[u]+
val[to[i]])
83
{
84
dp[to[i]]=dp[u]+
val[to[i]];
85
num[to[i]]=
num[u];
86
}
87
else
if
(dp[to[i]]==dp[u]+
val[to[i]])
88
{
89
num[to[i]]=(num[to[i]]+num[u])%
mod;
90
}
91
vis[to[i]]=
u;
92
}
93
}
94
}
95
96
inline
void
go()
97
{
98
for
(
int
i=
1
;i<=n;i++
)
99
if
(!
dfn[i]) dfs(i);
100
memset(head,-
1
,
sizeof
head); cnt=
0
;
101
for
(
int
i=
1
;i<=m;i++
)
102
if
(belong[st[i]]!=
belong[ed[i]])
103
{
104
add(belong[st[i]],belong[ed[i]]);
105
in
[belong[ed[i]]]++
;
106
}
107
topsort();
108
for
(
int
i=
1
;i<=divg;i++
)
109
{
110
if
(dp[i]>
ans)
111
{
112
ans=
dp[i];
113
ansnum=
num[i];
114
}
115
else
if
(dp[i]==ans) ansnum=(ansnum+num[i])%
mod;
116
}
117
printf(
"
%d\n%d\n
"
,ans,ansnum);
118
}
119
120
int
main()
121
{
122
read();
123
go();
124
return
0
;
125
}
