P3916 图的遍历 题解
本文最后修改于 851 天前,部分内容可能已经过时!
别人家的正解。。。。。。
#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;
}