RT，调了一年

思路大概两个月前就有所了解，一直口胡没写

注意新图要去重边，一个很好的写法是把可以建的边按字典序排序，跟上一个比较

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>

inline int max(int x,int y){return x>y?x:y;}

inline int min(int x,int y){return x<y?x:y;}

int n,m,MOD,cnt,Cnt,Ant,maxi,tarclock,colorclock,head[100005],
    Head[100005],dfn[100005],low[100005],dep[100005],
    size[100005],ind[100005],color[100005],f[100005],vis[100005];
    
std::queue<int> q;

std::stack<int> s;

struct edge{
    int v,next;
}e[1000005];

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

struct Edge{
    int v,next;
}E[1000005];

inline void Add(int u,int v){
    E[++Cnt].v=v;
    E[Cnt].next=Head[u];
    Head[u]=Cnt;
}

struct arr{
    int u,v;
}A[1000005];

inline bool cmp(arr x,arr y){
    if(x.u!=y.u)return x.u<y.u;
    return x.v<y.v;
}

inline void tarjan(int u){
    dfn[u]=low[u]=++tarclock;
    vis[u]=1;
    s.push(u);
    for(int i=head[u];i!=-1;i=e[i].next){
        int v=e[i].v;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v])low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
        colorclock++;
        while(1){
            int x=s.top();
            s.pop();
            vis[x]=0;
            color[x]=colorclock;
            size[colorclock]++;
    //      printf("%d in %d\n",x,colorclock);
            if(x==u)break;
        }
    }
}

inline void Rebuild(){
    for(int u=1;u<=n;u++){
        for(int i=head[u];i!=-1;i=e[i].next){
            int v=e[i].v;
            if(color[u]!=color[v]){
                A[++Ant].u=color[u];
                A[Ant].v=color[v];
            }
        }
    }
    std::sort(A+1,A+Ant+1,cmp);
    for(int i=1;i<=Ant;i++){
        if(A[i-1].u==A[i].u&&A[i-1].v==A[i].v)continue;
        ind[A[i].v]++;
        Add(A[i].u,A[i].v);
    }
//  for(int u=1;u<=n;u++){
    //  printf("the ind of %d is %d\n",u,ind[u]);
//  }
}

inline void topo(){
    for(int u=1;u<=colorclock;u++){
        if(!ind[u]){
            q.push(u);
            f[u]=1;
            dep[u]=size[u];
        }
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        maxi=max(maxi,dep[u]);
        for(int i=Head[u];i!=-1;i=E[i].next){
            int v=E[i].v;
            if(dep[v]<dep[u]+size[v]){
        //      printf("%d is updated by %d\n",v,u);
                dep[v]=dep[u]+size[v];
                f[v]=f[u]%MOD;
            }
            else if(dep[v]==dep[u]+size[v]){
                f[v]=(f[v]+f[u])%MOD;
            }
            ind[v]--;
            if(!ind[v]){
                q.push(v);
            }
        }
    }
}

inline void getans(){
    int ans=0;
    for(int i=1;i<=colorclock;i++){
        if(dep[i]==maxi){
            ans+=f[i];
            ans%=MOD;
        }
    }
//  for(int i=1;i<=colorclock;i++){
//      printf("%d:dep=%d f=%d\n",i,dep[i],f[i]);
//  }
    printf("%d\n%d\n",maxi,ans);
}

int main(){
    memset(head,-1,sizeof(head));
    memset(Head,-1,sizeof(Head));
    scanf("%d%d%d",&n,&m,&MOD);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i);
    }
    Rebuild();
    topo();
    getans();
}

最大半联通子图