啊缩点wa3个点求助啊

回复帖子

@issue_is_fw 2020-09-02 11:56 回复

自环也考虑了

但一直wa三个点

都说我第二问做了emm

检查好久没看出来~

#include <bits/stdc++.h>
using namespace std;
const int inf=36500;
const int maxn=1e6+10;
int n,m,dp[maxn];
struct edge{
    int u,to,nxt;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v){
    d[++cnt]=(edge){u,v,head[u]},head[u]=cnt;
}
int low[maxn],dfn[maxn],stac[maxn],vis[maxn],id,top,scc[maxn];
void tarjan(int u)
{
    low[u]=dfn[u]=++id,stac[++top]=u,vis[u]=1;
    for(int i=head[u];i;i=d[i].nxt )
    {
        int v=d[i].to;
        if( !dfn[v] )   tarjan(v),low[u]=min(low[u],low[v]);
        else if( vis[v] )   low[u]=min(low[u],dfn[v]);
    }
    if( dfn[u]==low[u] )
    {
        int temp,chu=inf;
        if( stac[top]==u )  chu=0;  
        while( temp=stac[top--] )
        {
            scc[temp]=u;
            vis[temp]=0;
            if( dp[temp]==0 ) dp[temp]=chu;//在环中,无限可能
            if( u==temp )   break; 
        }
    }
}
int in[maxn];
vector<int>vec[maxn];
void tuopu()
{
    queue<int>q;
    for(int i=1;i<=n+1;i++)
        if( i==scc[i]&&!in[i] ) q.push( scc[i] );
    dp[ scc[n+1] ]=1;
    while( !q.empty() )
    {
        int u=q.front(); q.pop();
        for(int i=0;i<vec[u].size();i++)
        {
            int v=vec[u][i];
            if( --in[v]==0 )    q.push( v );
            dp[v]+=dp[u];
            if( dp[v]>inf ) dp[v]=inf;
        }
    } 
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        int l,r; cin >> l >> r;
        add(r,l);
        if( l==r )  dp[l]=inf;
    }
    for(int i=1;i<=n+1;i++)
        if( !dfn[i] )   tarjan(i);
    for(int i=2;i<=cnt;i++)
    {
        int u=d[i].u,v=d[i].to;
        if( scc[u]==scc[v] )    continue;
        vec[ scc[u] ].push_back( scc[v] );//建立反向边
        in[ scc[v] ]++; 
    }
    tuopu();
    int maxx=0,shu=0;
    for(int i=1;i<=n+1;i++)
    {
        if( dp[i]>maxx )    maxx=dp[i],shu=1;
        else if( dp[i]==maxx )  shu++;
    }
    if( dp[scc[n+1]]==maxx )    shu--;
    if( maxx==inf ) cout << "zawsze\n";
    else    cout << maxx << '\n';
    cout << shu << endl;
    for(int i=1;i<=n;i++)
        if( dp[scc[i]]==maxx )  cout << i << " ";
}
@柳苏明 2020-10-11 21:57 回复 举报

你看这组数据

10 13
1 2
1 4
5 4
4 3
2 3
3 11
3 10
9 10
6 4
7 4
8 7
8 6
8 11

答案

3
1
8

应该在拓扑排序之前删掉除belong[n]外的入度为0的点

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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