一本通 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;
}
更多推荐
信息学奥赛一本通 1351:【例4
发布评论