求大佬帮看WA3个

回复帖子

@disangan333  2018-09-01 21:02 回复
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<vector>
#include<deque>
#include<set>
#include<map>
#define N 1000005
using namespace std;
struct Edge{
    int front,to,next;
}edges[N],edgesd[N];
int n,m,cnt,head[N],cnts,heads[N];
void add(int x,int y){
    edges[++cnt]={x,y,head[x]};
    head[x]=cnt;
}
void adds(int x,int y){
    edgesd[++cnts]={x,y,heads[x]};
    heads[x]=cnts;
}
int dfn[N],low[N],occ[N];
int stk[N],top,p[N];
int v[N],f[N],d[N],fs[N];
void Tarjan(int x){
    dfn[x]=low[x]=++dfn[0];
    stk[++top]=x;p[x]=1;    
    for(int i=head[x];i;i=edges[i].next){
        int y=edges[i].to;
        if(!dfn[y]){
            Tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(p[y])
            low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        ++occ[0];
        int xx,xxx=0;
        while(stk[top]!=x){
            xx=stk[top];
            p[xx]=0;
            occ[xx]=occ[0];
            top--;
            xxx=1;
        }
        if(xxx||(f[x]==36501))fs[occ[0]]=36501;
        p[x]=0;
        occ[x]=occ[0];
        top--;
    }
}
void Topsort(){
    queue<int>q;
    for(int i=1;i<=occ[0];i++){
        if(d[i]==0)
            q.push(i);
    }
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=heads[x];i;i=edgesd[i].next){
            int y=edgesd[i].to;
            if(--d[y]==0)
                q.push(y);  
            if(fs[y]>=36501)continue;
            fs[y]+=fs[x];
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(x==y)f[x]=36501;
        else add(y,x);
    }
    for(int i=1;i<=n+1;i++){
        if(!dfn[i])
            Tarjan(i);
    }
    for(int i=1;i<=cnt;i++){
        int x=edges[i].front,y=edges[i].to;
        if(occ[x]!=occ[y]){
            d[occ[y]]++;
            adds(occ[x],occ[y]);
        }   
    }
    if(!fs[occ[n+1]])fs[occ[n+1]]=1;
    Topsort();
    int maxx=0,xx=0;
    for(int i=1;i<=n;i++){
        f[i]=fs[occ[i]];
        if(f[i]>36501)f[i]=36501;
        if(f[i]>maxx)maxx=f[i],xx=1;
        else if(f[i]==maxx)xx++;
    }
    if(maxx==36501)printf("zawsze");
    else printf("%d",maxx);
    printf("\n%d\n",xx);
    for(int i=1;i<=n;i++){
        if(f[i]==maxx)
            printf("%d ",i);
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。