复习 C 语言
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define not !
#define and &&
#define or ||
#define r() fast_read()
#define f(inc, frm, to) for (size_t inc = frm; inc < to; ++inc)
typedef long long int ll;
#define MAX_N 100100
#define MAX_M 100100
int head[MAX_N], edge_cnt;
typedef struct Edge Edge;
struct Edge {
int to, nxt;
} edges[MAX_M];
void addEdge(int u, int v) {
edges[++edge_cnt] = (Edge) {v, head[u]};
head[u] = edge_cnt;
}
ll fast_read(void) {
ll n = 0, sign = 1;
char c = getchar();
while (c < 48 or c > 57) {
if (c == '-') sign = ~0;
c = getchar();
}
while (c >= 48 and c <= 57) {
n = (n << 1) + (n << 3) + (c ^ 48);
c = getchar();
}
return sign * n;
}
// ===================== SqStack =============
typedef int SElemType;
typedef struct {
SElemType* base;
SElemType* top;
size_t capacity;
} SqStack;
bool InitStack(SqStack* S, size_t capacity) {
if (capacity <= 0) return 0;
S->base = (SElemType*) malloc(capacity * sizeof(SElemType));
if (not S->base) return 0;
S->top = S->base;
S->capacity = capacity;
return 1;
}
bool StackEmpty(SqStack* S) {
return S->top == S->base;
}
bool StackFull(SqStack* S) {
return S->top - S->base == S->capacity;
}
size_t StackLength(SqStack* S) {
return S->top - S->base;
}
bool Push(SqStack* S, SElemType e) {
if (StackFull(S)) {
fprintf(stderr, "The stack is full!\n");
return 0;
}
*S->top++ = e;
return 1;
}
bool Pop(SqStack* S, SElemType* e) {
if (StackEmpty(S)) {
fprintf(stderr, "The stack is empty!\n");
return 0;
}
*e = *--S->top;
return 1;
}
SElemType GetTop(SqStack* S) {
if (StackEmpty(S)) return -0x7fffffff;
return *(S->top - 1);
}
void DestroyStack(SqStack* S) {
if (S->base) free(S->base);
S->top = S->base = NULL;
}
// ===================== SqStack =============
int n, m, indegrees[MAX_N];
void print_graph(void) {
putchar(10);
f(u, 1, n + 1) {
printf("Vertex %ld --> ", u);
for (int e = *(head + u); e; e = edges[e].nxt)
printf("[%d]\t", edges[e].to);
putchar(10);
}
}
void topo_sort(void) {
SqStack S;
InitStack(&S, MAX_N);
f(u, 1, n + 1) if (not *(indegrees + u)) Push(&S, u);
int topo[MAX_N], k = 0, u;
while (not StackEmpty(&S)) {
Pop(&S, &u);
*(topo + k++) = u;
for (int e = *(head + u), v; e; e = edges[e].nxt) {
v = edges[e].to;
if (not --indegrees[v]) Push(&S, v);
}
}
if (k < n) { puts("-1"); DestroyStack(&S); return; }
f(i, 0, k) printf("%d%c", *(topo + i), i == k - 1 ? 10 : 32);
DestroyStack(&S);
}
int main(int argc, char const *argv[]) {
// freopen("test.in", "r", stdin);
n = r(), m = r();
for (int u, v; m--;) {
u = r(), v = r();
addEdge(u, v);
++indegrees[v];
}
topo_sort();
// fclose(stdin);
return 0;
}
只有DAG(有向无环图)才有拓扑排序!
算法1:Using BFS to solve Topologic Sorting Problem.
#include <bits/stdc++.h>
using namespace std;
int n, m, u, v;
int main() {
cin >> n >> m;
vector<vector<int>> g(n + 1); // adjacency list
vector<int> indegrees(n + 1); // 入度表
// build the directed graph
while (m--) {
cin >> u >> v;
g[u].emplace_back(v);
++indegrees[v];
}
queue<int> q;
for (int i = 1; i <= n; ++i)
if (indegrees[i] == 0) q.emplace(i);
vector<int> ans;
while (not q.empty()) {
auto cur = q.front(); q.pop();
ans.emplace_back(cur);
for (const auto& nxt : g[cur])
if (--indegrees[nxt] == 0) q.emplace(nxt);
}
if (ans.size() == n) {
for (const auto& x : ans) cout << x << ' ';
} else {
cout << -1 << endl;
}
return 0;
}
算法2: Using DFS to solve Topologic Sorting Problem.
#include <bits/stdc++.h>
using namespace std;
int n, m, u, v;
bool dfs(vector<vector<int>>& g, int cur, vector<int>& states, vector<int>& ans) {
// base case
if (states[cur] == 1) return true; // The cycle has detected! (侦测到图中有环)
if (states[cur] == 2) return false;
states[cur] = 1; // mark as visiting (访问中)
for (const auto& nxt : g[cur])
if (dfs(g, nxt, states, ans)) return true;
states[cur] = 2; // mark as visited (访问过)
ans.emplace_back(cur);
return false;
}
int main() {
cin >> n >> m;
// adjacency list (邻接链表). 现代高级编程语言一般都用动态数组代替,可能只有C语言还在使用linked list
vector<vector<int>> g(n + 1);
// build the directed graph
while (m--) {
cin >> u >> v;
g[u].emplace_back(v);
}
// state O: UNKNOW, 1: VISITING, 2: VISITED
vector<int> states(n + 1, 0);
vector<int> ans;
// The graph may be has multiple connected components!!!
for (int i = 1; i <= n; ++i)
if (dfs(g, i, states, ans)) {
cout << -1 << endl; // The cycle has detected! (侦测到图中有环)
return 0;
}
std::reverse(begin(ans), end(ans));
for (const auto& x : ans) cout << x << ' ';
cout << endl;
return 0;
}