P3916 图的遍历 题解

本文最后修改于 771 天前，部分内容可能已经过时！

别人家的正解。。。。。。

#include <bits/stdc++.h>
using namespace std;

struct edge{
    int v,ne;
}a[100010];
int n,m,d[100010],h[100010],tmp;
void add(int x,int y){
    a[++tmp]=(edge){y,h[x]};
    h[x]=tmp;
}
void dfs(int x,int key)
{
    d[x]=key;
    for(int i=h[x];i!=0;i=a[i].ne)
    {
        if(d[a[i].v]==0)
        {
            dfs(a[i].v,key);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int liu,chen,i=1;i<=m;i++)
    {
        scanf("%d%d",&liu,&chen);
        add(chen,liu);
    }
    for(int i=n;i>=1;i--)
        if(d[i]==0)
            dfs(i,i);
    for(int i=1;i<=n;i++)
        printf("%d%c",d[i],i==n?'\n':' ');
    return 0;
}

自己做的半吊子解。。。。

#include <bits/stdc++.h>
#define MAX 100005
using namespace std;
int n,m,u[MAX],v[MAX],result[MAX];
bool check(int a,int b) {
    
    return false;
}
void dfs(int step) {
    if (result[now]) return;
    result[now]=st;
    for (int e=las[now];e;e=nxt[e])
        if (!u[to[e]]) dfs(to[e],st);
    return;
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d%d",u[i],v[i]);
    dfs(0);
    printf
    return 0;
}