HeYilin @ 2024-07-16 15:24:58
#include<bits/stdc++.h>
#define PII pair<int,int>
typedef long long int ll;
using namespace std;
const int maxn=2e6+10;
int n,m,val[maxn],u[maxn],v[maxn],mod;
int fir[maxn],Fir[maxn],sum,cnt,num;
int dfn[maxn],low[maxn],col[maxn],scc[maxn];
int indegree[maxn],ans,fans,dp[maxn],f[maxn],x,y;
queue<int>q;
stack<int>stk;
//map<int,map<int,int> >mp;
map<PII,bool>mp;
bool ins[maxn];
struct node{
int to,nxt;
}e[maxn],E[maxn];
void add_edge(int a,int b){
e[++cnt].to=b;
e[cnt].nxt=fir[a];
fir[a]=cnt;
}
void add(int a,int b){
E[++cnt].to=b;
E[cnt].nxt=Fir[a];
Fir[a]=cnt;
}
void tarjan(int x){
dfn[x]=low[x]=++num;
stk.push(x);ins[x]=1;
for(int i=fir[x];i;i=e[i].nxt){
int y=e[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}else if(ins[y])low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
sum++;
int t;
do{
t=stk.top();
stk.pop();ins[t]=0;
col[t]=sum;
scc[sum]+=val[t];
}while(x!=t);
}
}
void topsort(){
for(int i=1;i<=sum;i++)if(!indegree[i])dp[i]=scc[i],f[i]=1,q.push(i);
while(!q.empty()){
x=q.front();
q.pop();
for(int i=Fir[x];i;i=E[i].nxt){
y=E[i].to;
if(dp[y]<dp[x]+scc[y])dp[y]=dp[x]+scc[y],f[y]=f[x];
else if(dp[y]==dp[x]+scc[y])f[y]+=f[x];
f[y]%=mod;
// dp[y]=max(dp[y],dp[x]+scc[y]);
if(!--indegree[y])q.push(y);
}
}
for(int i=1;i<=n;i++){
if(dp[i]>ans)ans=dp[i],fans=f[i];
if(dp[i]==ans)fans=max(fans,f[i]);
}
}
int main(){
cin>>n>>m>>mod;
for(int i=1;i<=n;i++)val[i]=1;
for(int i=1;i<=m;i++){
cin>>u[i]>>v[i];
add_edge(u[i],v[i]);
}
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
cnt=0;
for(int i=1;i<=m;i++){
if(col[u[i]]!=col[v[i]]&&!mp[make_pair(col[u[i]],col[v[i]])])
add(col[u[i]],col[v[i]]),indegree[col[v[i]]]++,mp[make_pair(col[u[i]],col[v[i]])]=1;
}
topsort();
cout<<ans<<"\n"<<fans;
return 0;
}
/*
6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4
*/by HeYilin @ 2024-07-16 15:25:48
bb一句：我同桌一开始是怂恿我发这个标题的
by TangyixiaoQAQ @ 2024-07-16 15:26:20
@HeYilin qp
by TangyixiaoQAQ @ 2024-07-16 15:26:32
火钳刘明
by hanciyang @ 2024-07-16 15:26:38
@HeYilin qp
by hanciyang @ 2024-07-16 15:28:13
@HeYilin 「或崴流泥」
by HFBZ_MIT_MC @ 2024-07-16 15:37:17
t6kyukuykyuky7uk
by Sacred_Konnyaku_mMr @ 2024-07-16 16:00:29
蒟蒻改了好久才改出来，不得不说大佬的码分是真的独特 丑
#include<bits/stdc++.h>
#define PII pair<int,int>
typedef long long int ll;
using namespace std;
const int maxn=2e6+10;
int n,m,val[maxn],u[maxn],v[maxn],mod;
int fir[maxn],Fir[maxn],sum,cnt,num;
int dfn[maxn],low[maxn],col[maxn],scc[maxn];
int indegree[maxn],ans,fans,dp[maxn],f[maxn],x,y;
queue<int>q;
stack<int>stk;
//map<int,map<int,int> >mp;
map<PII,bool>mp;
bool ins[maxn];
struct node{
int to,nxt;
}e[maxn],E[maxn];
void add_edge(int a,int b){
e[++cnt].to=b;
e[cnt].nxt=fir[a];
fir[a]=cnt;
}
void add(int a,int b){
E[++cnt].to=b;
E[cnt].nxt=Fir[a];
Fir[a]=cnt;
}
void tarjan(int x){
dfn[x]=low[x]=++num;
stk.push(x);ins[x]=1;
for(int i=fir[x];i;i=e[i].nxt){
int y=e[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}else if(ins[y])low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
sum++;
int t;
do{
t=stk.top();
stk.pop();ins[t]=0;
col[t]=sum;
scc[sum]+=val[t];
}while(x!=t);
}
}
void topsort(){
for(int i=1;i<=sum;i++)if(!indegree[i])dp[i]=scc[i], ans = max(ans, scc[i]),f[i]=1,q.push(i); //这边要在一开始就更新ans
while(!q.empty()){
x=q.front();
q.pop();
for(int i=Fir[x];i;i=E[i].nxt){
y=E[i].to;
if(dp[y]<dp[x]+scc[y])dp[y]=dp[x]+scc[y],f[y]=f[x], dp[y] %= mod;
else if(dp[y]==dp[x]+scc[y])f[y]+=f[x];
f[y]%=mod;
// dp[y]=max(dp[y],dp[x]+scc[y]);
if(!--indegree[y])q.push(y), ans = max(ans, dp[y] % mod);
}
}
for (int i = 1; i <= sum; ++i) {
if(dp[i] == ans) fans += f[i], fans %= mod; //这里是加上而不是区max，因为有可能有多条最长链，所以要加起来
}
}
int main(){
cin>>n>>m>>mod;
for(int i=1;i<=n;i++)val[i]=1;
for(int i=1;i<=m;i++){
cin>>u[i]>>v[i];
add_edge(u[i],v[i]);
}
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
cnt=0;
for(int i=1;i<=m;i++){
if(col[u[i]]!=col[v[i]]&&!mp[make_pair(col[u[i]],col[v[i]])])
add(col[u[i]],col[v[i]]),indegree[col[v[i]]]++,mp[make_pair(col[u[i]],col[v[i]])]=1;
}
topsort();
cout<<ans<<"\n"<<fans;
return 0;
}
/*
6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4
*/已AC
by wangtairan114 @ 2024-07-16 16:07:28
qp