这么好的代码怎么死循环了,(循环处已指出>wQ

P2272 [ZJOI2007] 最大半连通子图

Xing_ke @ 2020-03-25 00:19:02

#include<bits/stdc++.h>
#define M 1000005
using namespace std;
int n,m,mod;

struct Node{
    int fr,to,nxt;
}e[M];
int cnt=0,head[M];
void add1(int fr,int to){
    cnt++;
    e[cnt].fr=fr;
    e[cnt].to=to;
    e[cnt].nxt=head[fr];
    head[fr]=cnt;
}

struct node{
    int fr,to,nxt;
}e2[M];
int cntt=0,head2[M];
void add2(int fr,int to){
    cntt++;
    e2[cntt].fr=fr;
    e2[cntt].to=to;
    e2[cntt].nxt=head2[fr];
    head2[fr]=cntt;
}

int t=0,gg=0;
stack<int> s;
int id[M],sz[M];
int dfn[M],low[M];
void taj(int x){
    dfn[x]=low[x]=++t; s.push(x);
    for(int i=head[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(!dfn[y]){
            taj(y);
            low[x]=min(low[x],low[y]);
        }else if(!id[y]){
            low[x]=min(low[x],dfn[y]);
        }
    } int u;
    if(low[x]==dfn[x]){
        gg++;
        do{
            u=s.top();s.pop();
            id[u]=gg;sz[gg]++;
        }while(x!=u);
    }
}

int us[M];
int f[M],g[M];
void topu(){
    for(int x=1;x<=n;++x){
        f[x]=sz[x];
        g[x]=1;
        for(int i=head[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(id[x]==id[y]) continue;
            add2(id[x],id[y]);
        }
    }
    for(int x=gg;x>=1;x--){
        for(int i=head2[x];i;e2[i].nxt){
            int y=e2[i].to;
            if(us[y]==x) continue;//<——here!! 
            us[y]=x;
            if(f[y]<f[x]+sz[y]){
                f[y]=f[x]+sz[y];
                g[y]=g[x];
            }else if(f[y]==f[x]+sz[y]){
                g[y]+=g[x];
                g[y]%=mod;
            }
        }
    }
}

inline int read(){
    int x=0;int f=1;char ch=getchar();
    while(!isdigit(ch)){ if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int ans=0,tmp=0;
int main(){
    n=read(),m=read(),mod=read();
    for(int i=1;i<=m;++i){
        int x=read(),y=read();
        add1(x,y);
    }
    for(int i=1;i<=n;++i)
        if(!dfn[i]) taj(i);

    topu();

    for(int i=1;i<=gg;++i){
        if(f[i]>ans){
            ans=f[i];
            tmp=g[i];
        }else if(f[i]==ans){
            tmp+=g[i];
            tmp%=mod;
        }
    }
    printf("%d\n%d\n",ans,tmp);
    return 0;
}

借鉴题解xiaofulll dalao的(第一页 ヾ(◍°∇°◍)ノ゙

加油,祝你全家健康>wQ

谢谢啦~


by Xing_ke @ 2020-03-25 00:19:32

静坐


by Xing_ke @ 2020-03-25 00:20:07

先下线了,dalao找到了@我下~


by Kinandra @ 2020-03-25 07:42:37

应该是 i=e2[i].nxt 吧


by Kinandra @ 2020-03-25 07:43:02

凌晨发帖可真行


by Xing_ke @ 2020-03-25 12:33:41

蟹蟹蟹蟹~


by Xing_ke @ 2020-03-25 12:34:51

不凌晨没办法(菜是原罪QWQ


|