Algorithm14.6 图的遍历与搜索

#include <iostream>
using namespace std;
#define maxpoint 100010
#define maxedge 1000010
int n, m, ta, tb, vis[maxpoint];
struct ed {
    int from, to;
    bool operator < (const ed e) const { if (from == e.from) return to > e.to;return from >e.from;}
}t[maxedge];
struct node {
    int to, next;
}edge[maxedge];int head[maxpoint], tot;
#include <queue>
queue<int>pq;
#include <cstring>
#define cl(a, b) memset(a, b, sizeof(a))
#include <algorithm>

void addedge(int from, int to) {
    edge[++tot].to = to;
    edge[tot].next = head[from];
    head[from] = tot;
}

void dfs(int val) {
    printf("%d ", val);
    for (int i = head[val]; i; i=edge[i].next) {
        int to = edge[i].to;
        if (!vis[to]) {vis[to] = 1; dfs(to);}
    }
}

void bfs(int val) {
    pq.push(val);
    while (!pq.empty()) {
        int nw = pq.front();pq.pop();
        printf("%d ", nw);
        for (int i = head[nw]; i; i=edge[i].next) {
            int to = edge[i].to;
            if (!vis[to]) {vis[to] = 1;pq.push(to);}
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) scanf("%d%d", &t[i].from, &t[i].to);
    sort(t+1, t+m+1);
//    for (int i = 1; i <= m; ++i) printf("%d %d\n", t[i].from, t[i].to);
    for (int i = 1; i <= m; ++i) addedge(t[i].from, t[i].to);
    vis[1] = 1;dfs(1);
    printf("\n");cl(vis, 0);
    vis[1] = 1;bfs(1);
    return 0;
}

#include <iostream>
using namespace std;
#define maxpoint 100010
#define maxedge 100010
int n, m, ta, tb, vis[maxpoint], ans;
struct node {
    int to, next;
}edge[maxedge];int head[maxpoint], tot;
#include <cstring>
#define cl(a, b) memset(a, b, sizeof(a))

void addedge(int from, int to) {
    edge[++tot].to = to;
    edge[tot].next = head[from];
    head[from] = tot;
}

void dfs(int val) {
    ans = max(ans, val);
    for (int i = head[val]; i; i=edge[i].next) {
        int to = edge[i].to;
        if (!vis[to]) {vis[to] = 1;dfs(to);}
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &ta, &tb);
        addedge(ta, tb);
    }
    for (int i = 1; i <= n; ++i) {
        cl(vis, 0);vis[i] = 1;ans = 0;
        dfs(i);
        printf("%d ", ans);
    }
    return 0;
}