526互联

Uva--10305 Ordering Tasks(拓扑排序/dfs)

发布时间 2023-05-26 16:00:33作者: 57one

记录
15:42 2023-5-26

https://onlinejudge.org/external/103/p10305.pdf

reference:《算法竞赛入门经典第二版》例题6-15

拓扑排序，存在有向环的图没有解。不包含有向环的有向图称为有向无环图（Directed Acyclic Graph，DAG）
书上给出来的是使用dfs方式进行拓扑排序，注意访问状态visited[]数组的使用，如果dfs途中又访问了已经正在访问的节点，说明是存在回路。
另一种方式是我之前学过的，《数据结构与算法分析》中的拓扑排序，类似于bfs的方法，加入队列是入度为0的节点，从队列中取出一个节点后，更新其它节点的入度并将入度为0的点再放入队列。

使用dfs

#include<cstdio>
#include<cstring>
#define MAX_N 1000
using namespace std;
typedef long long ll;
typedef unsigned int uint;
const int INF = 0x3f3f3f3f;

int G[MAX_N][MAX_N];
int visited[MAX_N]; // 0表示未访问 1表示访问过 -1表示正在访问
int tops[MAX_N];
int t;
int N, M;

bool dfs(int u) {
    visited[u] = -1;
    for(int i = 1; i <= N; i++) {
        if(G[u][i]) {
            //i访问到正在访问的节点 表示有回环
            if(visited[i] == -1) return false;
            else if(!visited[i] && !dfs(i)) return false;
        }
    }
    visited[u] = 1;
    tops[t--] = u;
    return true;
}

bool solve() {
    t = N;
    memset(visited, 0, sizeof(visited));
    for(int i = 1; i <= N; i++) {
        if(!visited[i]){
            if(!dfs(i)) return false;
        }
    }
    return true;
}

int main () {
    while (scanf("%d%d", &N, &M) == 2 && N) {
        memset(G, 0, sizeof(G));
        int s, e;
        for(int i = 0; i < M; i++) {
            scanf("%d%d", &s, &e);
            G[s][e] = 1;
        }
        if(solve()) {
            for(int i = 1; i < N; i++) {
                printf("%d ", tops[i]);
            }
            printf("%d\n", tops[N]);
        } else {
            printf("No\n");
        }
    }
}

使用类bfs

#include<cstdio>
#include<cstring>
#include<queue>
#define MAX_N 1000
using namespace std;
typedef long long ll;
typedef unsigned int uint;
const int INF = 0x3f3f3f3f;

int G[MAX_N][MAX_N];
int indegree[MAX_N];
int tops[MAX_N];
int t = 1;
int count = 0;
int N, M;
queue<int> q;

bool topsort() {
    for(int i = 1; i <= N; i++) {
        if(indegree[i] == 0) {
            q.push(i);
            count++;
        }
    }
    while (!q.empty()) {
        int u = q.front();q.pop();
        tops[t++] = u;
        for(int i = 1; i <= N; i++) {
            if(G[u][i]) {
                if(--indegree[i] == 0) {
                    q.push(i);
                    count++;
                }
            }
        }
    }
    if(count != N) return false;
    return true;
}

int main () {
    while (scanf("%d%d", &N, &M) == 2 && N) {
        memset(G, 0, sizeof(G));
        memset(indegree, 0, sizeof(indegree));
        count = 0;
        t = 1;
        int s, e;
        for(int i = 0; i < M; i++) {
            scanf("%d%d", &s, &e);
            G[s][e] = 1;
            indegree[e]++;
        }
        if(topsort()) {
            for(int i = 1; i < N; i++) {
                printf("%d ", tops[i]);
            }
            printf("%d\n", tops[N]);
        } else {
            printf("No\n");
        }
    }
}