AcWing 848. 贴一个dfs的代码
原题链接
简单
作者:
Tokai_Teio
,
2024-04-09 12:41:25
,
所有人可见
,
阅读 1
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int N = 100010;
int h[N],e[N],ne[N],idx;
int st[N];
stack<int> stk;
int n,m;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
// 0 未访问
// 1 访问当前节点,但邻接节点未访问完
// 2 访问完成
bool dfs(int u)
{
st[u]=1;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
// 有向图,不能判断j!=fa,因为j能走到fa也是环
// 无向图时需要判断j!=fa
if(st[j]==1)
{
return false;
}
else
{
if(st[j]==0)
{
if(dfs(j)==false) return false;
}
}
}
st[u]=2;
stk.push(u);
return true;
}
bool dfs_traverse()
{
bool ans = true;
for(int i=1;i<=n;i++)
{
if(st[i]==0) ans&=dfs(i);
}
return ans;
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
}
if(dfs_traverse())
{
while(stk.size())
{
cout<<stk.top()<<" ";
stk.pop();
}
}
else
{
cout<<"-1";
}
return 0;
}