dengjunhaodejia09 @ 2023-04-18 19:24:25
#include <bits/stdc++.h>
using namespace std;
int ppt;
struct edng{
int to,nxt;
}e[1000002];
int cnt,head[100002],color[100002];
int bbb=0,ans=0;
bool vis[100005];
int dfn[100006],low[100005],gshu[100005];
bool kun[100005];
stack <int> s;
inline int read(){
int x=0,f=1,ch=getchar();
for(;!isdigit(ch);ch=getchar()) f=(ch=='-')?-1:1;
for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
void dfs(int x){
bbb++;
vis[x]=true;
dfn[x]=low[x]=bbb;
s.push(x);
for(int i=head[x];i;i=e[i].nxt){
if(dfn[e[i].to]==false){
dfs(e[i].to);
low[x]=min(low[x],low[e[i].to]);
}else if(vis[e[i].to]) low[x]=min(low[x],dfn[e[i].to]);
}
if(low[x]==dfn[x]){
ans++;
int tmp=-1;
do{
tmp=s.top();
s.pop();
color[tmp]=ans;
vis[tmp]=0;
gshu[ans]++;
}while(tmp!=x);
}
}
int hhh[100005];
int Max=INT_MIN;
int ll=0;
int AK[100005];
int aa[100005];
inline int dfs(int yanse,int sum){
kun[yanse]=true;
int o=0,kkk=0;
int gg=0;
for(int i=head[yanse];i;i=e[i].nxt){
int rjl=e[i].to;
if(kun[rjl]==false){
kkk=max(kkk,dfs(rjl,sum+gshu[yanse]));
}
//2 3 1 4 5 6 7
if(kun[rjl]==true){
if(o<AK[rjl]){
gg=aa[rjl];
o=AK[rjl];
}else if(o==AK[rjl]){
gg+=aa[rjl];
}
}
}
hhh[sum+o+gshu[yanse]]+=max(gg,1);
hhh[sum+o+gshu[yanse]]=hhh[sum+o+gshu[yanse]]%ppt;
Max=max(sum+o+gshu[yanse],Max);
AK[yanse]=max(o,kkk)+gshu[yanse];
aa[yanse]=max(gg,1);
return o+gshu[yanse];
}
struct node{
int xx,yy;
}hi[1000005];
int cmp(node bbc,node ccb){
if(bbc.xx!=ccb.xx){
return bbc.xx<ccb.xx;
}else{
return bbc.yy<ccb.yy;
}
}
int cmpp(node bbc,node ccb){
if(color[bbc.xx]!=color[ccb.xx]){
return color[bbc.xx]<color[ccb.xx];
}else{
return color[bbc.yy]<color[ccb.yy];
}
}
int main(){
int n,m;
cin>>n>>m>>ppt;
for(int i=1;i<=m;i++){
int x,y;
hi[i].xx=read();
hi[i].yy=read();
}
sort(hi+1,hi+m+1,cmp);
for(int i=1;i<=m;i++){
if(hi[i].xx==hi[i-1].xx && hi[i].yy==hi[i-1].yy)continue;
if(hi[i].xx==hi[i].yy){
continue;
}else{
cnt++;
e[cnt].to=hi[i].yy;
e[cnt].nxt=head[hi[i].xx];
head[hi[i].xx]=cnt;
}
}
int sum=0;
for(int i=1;i<=n;i++)if(!dfn[i])dfs(i);
memset(head,0,(ans+1)*sizeof(int));
memset(e,0,(m+1)*sizeof(edng));
cnt=0;
sort(hi+1,hi+m+1,cmpp);
for(int i=1;i<=m;i++){
if(color[hi[i].xx]==color[hi[i-1].xx] && color[hi[i].yy]==color[hi[i-1].yy])continue;
if(color[hi[i].xx]==color[hi[i].yy]){
continue;
}else{
cnt++;
e[cnt].to=color[hi[i].yy];
e[cnt].nxt=head[color[hi[i].xx]];
head[color[hi[i].xx]]=cnt;
}
}
for(int i=1;i<=ans;i++){
int l=dfs(i,0);
}
//
// for(int i=1;i<=ans;i++){
// cout<<AK[i]<<" ";
// }
// cout<<endl;
cout<<Max<<endl<<hhh[Max];
return 0;
}
by djy123456 @ 2024-07-15 13:51:49
@dengjunhaodejia09
没%
orz