萌新求助
查看原帖
萌新求助
661342
righting楼主2022/7/29 19:40

为什么这样的思路会错呢?

#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <queue>
using namespace std;
const int maxn=1e5+10;
int n,m,tim,top;
int ans[maxn];
int dfn[maxn],stac[maxn],head[maxn<<2],cnt;
int low[maxn];
bool vis[maxn];
int col[maxn],co;
int ed[maxn];
struct edge
{
    int next,to;
}e[maxn];
void add(int u,int v)
{
    e[++cnt].next=head[u];
    e[cnt].to=v;
    head[u]=cnt;
    return ;
}
void tarjan(int x)
{
    low[x]=dfn[x]=++tim;
    stac[++top]=x;
    vis[x]=true;
    ans[x]=x;
    for (int i=head[x];i;i=e[i].next)
    {
        int v=e[i].to;
        if (!dfn[v])
        {
            tarjan(v);
            low[x]=min(low[x],low[v]);
            ans[x]=max(ans[x],ans[v]);
        }
        else if (vis[v])
        {
            low[x]=min(low[x],low[v]);
            ans[x]=max(ans[x],ans[v]);
        }
    }
    if (dfn[x]==low[x])
    {
        int last;
        int mix=ans[x];
        col[x]=++co;
        int t=0;
        ed[++t]=x;
        while (1)
        {
            last=stac[top--];
            col[last]=co;
            mix=max(mix,ans[last]);
            if (last==x) break;
            ed[++t]=last;
        }
        for (int i=1;i<=t;i++)
        {
            ans[ed[t]]=mix;
        }
    }
    return  ;
}
int main ()
{
    scanf ("%d%d",&n,&m);
    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);
    }
    for (int i=1;i<=n;i++)
    {
        printf ("%d ",ans[i]);
    }
    system ("pause");
    return 0;
}

2022/7/29 19:40
加载中...