求助一个疑问#2
查看原帖
求助一个疑问#2
695622
Nicole_o楼主2022/8/2 14:52
#include <iostream>

using namespace std;
int n,m;
int head[50005],cnt;
int dfn[50005],low[50005],Stack[50005],s[50005],c[50005],visit[50005],tim,top,sum;
struct Edge
{
    int from,to,next;
}edge[1000005];
void Head(int u,int v,int s)
{
     cnt++;
     edge[cnt].from = u;
     edge[cnt].to   = v;
     edge[cnt].next = head[u];
     head[u]      = cnt;
     if(s==2)   Head(v,u,1);
}
void Targan(int u)
{
    dfn[u] = low[u] = ++tim;
    visit[u] = 1;
    Stack[top++] = u;
    for(int i = head[u];i;i = edge[i].next)
    {
        int v = edge[i].to;
        if(!dfn[v])
        {
            Targan(v);
            low[u] = min(low[u],low[v]);
        }
        else if(visit[v])
            low[u] = min(low[u],low[v]);
    }
    if(low[u]==dfn[u])
    {
        while(1)
        {
            int y = Stack[--top];
            s[y] = u;
            c[u]++;
            visit[y] = 0;
            if(y==u)
            {
                break;
            }
        }
        sum = max(sum,c[u]);
    }
}

void Count()
{
    int u;
    for(int i=1;i<=n;i++)
    {
        if(c[i]==sum)
        {
            u = i;
            break;
        }
    }
    cout<<sum<<endl;
    for(int i=1;i<=n;i++)//此处存疑,为啥要从1开始遍历,而不是从u开始遍历,u代表的点不就是强连通分量里最小的点吗???
    {
        if(s[i]==u) cout<<i<<" ";
    }
}
int main()
{
    int u,v,t;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>t;
        Head(u,v,t);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])     Targan(i);
    /*for(int i=1;i<=n;i++)
        cout<<s[i]<<" ";
    cout<<endl;*/
    Count();
    return 0;
}

数据2报错,把i=u改成i=1就对了,为什么???求助???

2022/8/2 14:52
加载中...