DFS
// (遍历)到达顺序:DFS序列
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 100010;
int n, m;
struct Node
{
int id;
Node *next;
Node(int _id): id(_id), next(NULL) {}
}*head[N];
bool st[N];
void add(int a, int b) // 头插法
{
Node *p = new Node(b);
p->next = head[a];
head[a] = p;
}
void dfs(int u)
{
st[u] = true;
printf("%d ", u);
for (Node *p = head[u]; p; p = p->next)
{
int j = p->id;
if(!st[j])
dfs(j);
}
}
int main()
{
scanf("%d%d", &n, &m);
while(m -- )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
// 处理图不连通时的情况
for (int i = 1; i <= n; i ++ )
if(!st[i])
dfs(i);
return 0;
}
BFS
// BFS用于求最短路问题
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010, M = 100010;
int n, m;
struct Node
{
int id;
Node *next;
Node(int _id): id(_id), next(NULL) {}
}*head[N];
bool st[N];
void add(int a, int b) // 头插法
{
Node *p = new Node(b);
p->next = head[a];
head[a] = p;
}
void bfs(int u)
{
queue<int> q;
q.push(u);
st[u] = true;
while(q.size())
{
int t = q.front();
q.pop();
printf("%d ", t);
for (Node *p = head[t]; p; p = p->next)
{
if(!st[p->id])
{
st[p->id] = true;
q.push(p->id);
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
while(m -- )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
// 处理图不连通时的情况,一般不用处理
for (int i = 1; i <= n; i ++ )
if(!st[i])
bfs(i);
return 0;
}