信息学奥赛一本通 1351：【例4

一本通 1351：【例4"/>

信息学奥赛一本通 1351：【例4

【题目链接】

ybt 1351：【例4-12】家谱树
洛谷 B3644 【模板】拓扑排序 / 家谱树

【题目考点】

1. 图论 拓扑排序

【解题思路】

要求序列中“每个人的后辈都比那个人后列出”。
如果这样建图：每个人是一个顶点。如果a是b的父辈，那么有一条从a到b的有向边<a, b>。
根据拓扑排序的定义：如果从a到b有一条路径，那么b在拓扑排序中在a的后面。
那么这个图的拓扑排序可以满足题目对所求的序列的要求。
因此这是个拓扑排序模板题，建图，求拓扑排序。

【题解代码】

解法1：使用vector邻接表

#include<bits/stdc++.h>
using namespace std;
#define N 105
vector<int> edge[N];
int n, deg[N];//deg[i]:顶点i的入度 
void init()//建图 
{int f, t;cin >> n;for(f = 1; f <= n; ++f){while(cin >> t && t != 0){edge[f].push_back(t);deg[t]++;}}
}
void topoSort()//拓扑排序 
{queue<int> que;for(int i = 1; i <= n; ++i)if(deg[i] == 0){cout << i << ' ';que.push(i);}while(que.empty() == false){int u = que.front();que.pop();for(int v : edge[u]){deg[v]--;if(deg[v] == 0){cout << v << ' ';que.push(v);}}}
}
int main()
{init();topoSort();return 0;
}

解法2：使用邻接矩阵

#include<bits/stdc++.h>
using namespace std;
#define N 105
int n, edge[N][N], deg[N];//deg[i]:顶点i的入度 
void init()//建图 
{int f, t;cin >> n;for(f = 1; f <= n; ++f){while(cin >> t && t){edge[f][t] = 1;deg[t]++;}}
}
void topoSort()//拓扑排序 
{queue<int> que;for(int i = 1; i <= n; ++i)if(deg[i] == 0){cout << i << ' ';que.push(i);}while(que.empty() == false){int u = que.front();que.pop();for(int v = 1; v <= n; ++v){if(edge[u][v]){deg[v]--;if(deg[v] == 0){cout << v << ' ';que.push(v);}}}}
}
int main()
{init();topoSort();return 0;
}