92分求助T_T
查看原帖
92分求助T_T
459149
P2501楼主2022/10/9 18:58

#5 #6 WA

#include<bits/stdc++.h>
using namespace std;
#define maxn 10010
#define maxm 50010
inline int read(){
    int x=0;char c=' ';
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}
int n,m,cnt,ans;
vector<int> g[maxn],gnew[maxn];
int weight[maxn];
int dfn[maxn],low[maxn],timer;
int visit[maxn],stk[maxn],it,belong[maxn];
void tarjan(int u){
    dfn[u]=low[u]=timer++;
    visit[u]=1;stk[++it]=u;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        if(visit[v])low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        cnt++;
        while(1){
            belong[stk[it]]=cnt;
            // cout<<cnt;
            visit[stk[it]]=0;
            weight[cnt]++;
            if(stk[it]==u){it--;break;}
            it--;
        }
    }
}
int visit2[maxn],degree[maxn];
int main(){
    n=read();m=read();
    for(int i=0;i<m;i++){
        int u=read(),v=read();g[v].push_back(u);// 反向建边;最后统计入度而非出度
    }
    for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;i++){
        for(int j=0;j<g[i].size();j++){
            if(belong[g[i][j]]!=belong[i])gnew[belong[i]].push_back(belong[g[i][j]]);
        }
    }
    for(int i=1;i<=cnt;i++){
        for(int j=0;j<gnew[i].size();j++){
            degree[gnew[i][j]]++;
        }
    }
    bool bo=1;int num=0;
    for(int i=1;i<=cnt;i++){
        if(!degree[i]){num++;ans=weight[i];}
        if(num>1)bo=0;
    }
    if(bo)cout<<ans;
    else cout<<0;

    return 0;
}

这两个点都可以确定正解是num(入度为0的顶点数)应该为1并输出ans;但程序错误地得到了num=2,以至于这两个点最终都错误地输出了0。但我真的没找到问题在哪里

2022/10/9 18:58
加载中...