以前做過poj的一個(gè)判斷圖是否為弱連通的題，然后，這個(gè)題和poj那個(gè)差不多。
先強(qiáng)連通縮點(diǎn)，然后重新構(gòu)圖，然后找出包含點(diǎn)數(shù)最多的 鏈 ，統(tǒng)計(jì)個(gè)數(shù)即可，可以用拓?fù)渑判蚋銅
?
pS：重新構(gòu)圖時(shí)有重邊，然后導(dǎo)致統(tǒng)計(jì)方案數(shù)的重復(fù)。。wa了好久。。還是wzc神犇告訴我這個(gè)蒟蒻的。。
?
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
}
?
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
