定个小目标啊,这几天学会它
拓扑排序是一个排序规则,求的是一个序列,并且序列不唯一
在图论中,拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序列。
且该序列必须满足下面两个条件:
**注意:只有有向无环图(DAG)才有拓扑排序**
拓扑排序过程中,队列中的元素始终唯1个,则拓扑排序序列唯一,反之,不然!!!
x
const int MAX_N = 1e5 + 5;
int q[MAX_N], ans[MAX_N]; //队列, 拓扑排序序列
int head[MAX_N], v[MAX_N], next[MAX_N], to[MAX_N], pen[MAX_N], edge_cnt; // 构造链式前向星
int n, cnt_ans;
inline void add_edge(int a, int b, int c) { //a->b = c
to[++edge_cnt] = b;
v[edge_cnt] = c;
next[edge_cnt] = head[a];
head[a] = edge_cnt;
++pen[b]; // b节点入度加一
}
void input1() {
for (int i = 1; i <= n - 1; i++) {
int a, b, c; // a->b = c
scanf("%d %d %d", &a, &b, &c);
add_edge(a, b, c);
}
}
void input2() { //默认边权为1
for (int i = 1; i <= n - 1; i++) {
int a, b; // a->b = c
scanf("%d %d", &a, &b);
add_edge(a, b, 1);
}
}
void output() {
for (int i = 1; i <= n; i++) {
for (int j = head[i]; j; j = next[j]) {
printf("(%d->%d = %d)\t", i, to[j], v[j]);
}
putchar('\n');
}
return ;
}
int main() {
scanf("%d", &n);
input2();
int l = 0, r = 0;
for (int i = 1; i <= n; i++) {
if (pen[i] == 0) q[r++] = i; //入队列
}
output();
while (l < r) {
int tp = q[l++];
ans[cnt_ans++] = tp; // 输出度为0的节点
for (int i = head[tp]; i; i = next[i]) {
//printf("%d->%d = %d\n", tp, to[i], v[i]);
//与节点tp连接的节点入度减一
if (--pen[to[i]] == 0) {
q[r++] = to[i]; // 进行入队
}
}
}
if (cnt_ans == n) {
for (int i = 0; i < n; i++) {
i && putchar(' ');
printf("%d", ans[i]);
}
} else printf("自环\n");
return 0;
}
/*
6
1 3 1000
1 4 10
4 5 50
4 6 100
4 2 100
*/
/*
10
7 5
5 2
2 1
4 10
10 3
3 1
6 8
8 9
9 1
*/
利用dfs
xxxxxxxxxx
int n, m;
int cnt_edge, head[MAX_N], next[MAX_N], to[MAX_N], rudu[MAX_N];
inline void add_edge(int a, int b) {
++rudu[b];
to[++cnt_edge] = b;
next[cnt_edge] = head[a];
head[a] = cnt_edge;
return ;
}
int ans[MAX_N], flag, vis[MAX_N];
void Topological_sorting(const int& cnt) { //dfs
if (cnt == n) { //输出拓扑排序序列
for (int i = 0; i < n; i++) {
printf("%d", ans[i]);
}
flag = 1;
putchar('\n');
}
for (int i = 1; i <= n; i++) {
if (vis[i] || rudu[i]) continue;
ans[cnt] = i;
vis[i] = 1;
for (int j = head[i]; j; j = next[j]) { //与该点连接的点的入度减1
--rudu[to[j]];
}
Topological_sorting(cnt + 1);
// 回溯
vis[i] = 0;
for (int j = head[i]; j; j = next[j]) ++rudu[to[j]];//与该点连接的点的入度加1
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
int a, b;
scanf("%d %d", &a, &b);
add_edge(a, b);
}
Topological_sorting(0);
if (flag) printf("No\n"); //存在环
return 0;
}
对于输出最小的拓扑排序序列,得用优先队列
完工