dfs

输入格式

第一行包含两个整数 $n$ 和 $m$。

接下来 $m$ 行，每行包含两个整数 $x$ 和 $y$，表示存在一条从点 $x$ 到点 $y$ 的无向边 ($x$,$y$)。

输入

5 4
1 2
1 3
1 4
3 5

输出

1 2 3 5 4 

c++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;

const int N = 510;

int n, m;
bool st[N];

struct Node
{
    int id; // 编号
    int w;  // 权值
    Node* next;
    Node(int _id) : id(_id), next(NULL){}
} *head[N];     // 邻接表

void add(int a, int b)
{
    Node* p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

void dfs(int u)
{
    stack<int> s;
    s.push(u);
    st[u] = true;

    while (!s.empty())
    {
        int t = s.top();
        s.pop();
        cout << t << ' ';

        for (auto p = head[t]; p; p = p->next)
        {
            int j = p->id;
            if (!st[j])
            {
                s.push(j);
                st[j] = true;
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    for (int i = 1; i <= n; i ++ )
        if (!st[i]) dfs(i);

    return 0;
}

bfs

输入

5 4
1 2
1 3
1 4
3 5

输出

1 4 3 2 5 

c++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 510, M = 100010, INF = 0x3f3f3f3f;

int n, m;
bool st[N];

struct Node
{
    int id; // 编号
    int w;  // 权值
    Node* next;
    Node(int _id) : id(_id), next(NULL){}
} *head[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();
        cout << t << ' ';

        for (auto p = head[t]; p; p = p->next)
        {
            int j = p->id;
            if (!st[j])
            {
                st[j] = true;
                q.push(j);
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    for (int i = 1; i <= n; i ++ )
        if (!st[i]) bfs(i);

    return 0;
}