[poj2367]Genealogical tree_拓扑排序
Genealogical tree poj-2367
题目大意：给你一个n个点关系网，求任意一个满足这个关系网的序列，使得前者是后者的上级。
注释：1<=n<=100.
想法：刚刚学习toposort，什么是toposort?
就是每一个点的遍历或选取有先决条件，那么我们可以通过队列或者栈将控制当前点的点先遍历，这样弹栈或出队的序列，就是toposort的结果
我们先附上模板
int v[100100];//入度
bool map[110][110]={false};//是否存在控制与被控制
int ans[110];//出队序列
int tot;
int n;void toposort()
{
queue<int>q;
for(int i=1;i<=n;i++)
{
if(!v[i]) q.push(i);
}
while(q.size())//其实toposort不同于spfa和bfs在于时间复杂度是O(n)的
{
int x=q.front(); q.pop(); ans[++tot]=x;//直接更新
for(int i=1;i<=n;i++)
{
if(map[x][i]==1)
{
v[i]--;
if(v[i]==0) q.push(i);
}
}
}
}
最后，附上丑陋的代码... ...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int v[100100];//入度
bool map[110][110]={false};//是否存在控制与被控制
int ans[110];//出队序列
int tot;
int n;void toposort()
{
queue<int>q;
for(int i=1;i<=n;i++)
{
if(!v[i]) q.push(i);
}
while(q.size())//其实toposort不同于spfa和bfs在于时间复杂度是O(n)的
{
int x=q.front(); q.pop(); ans[++tot]=x;//直接更新
for(int i=1;i<=n;i++)
{
if(map[x][i]==1)
{
v[i]--;
if(v[i]==0) q.push(i);
}
}
}
}
void original()
{
memset(map,false,sizeof map);
memset(ans,0,sizeof ans);
tot=0;
memset(v,0,sizeof v);
}
int main()
{
while(~scanf("%d",&n))
{
original();
for(int a,i=1;i<=n;i++)
{
while(1)
{
scanf("%d",&a);
if(!a) break;
v[a]++;
map[i][a]=1;
map[a][i]=1;
}
}
toposort();
for(int i=1;i<=tot;i++)
{
printf("%d ",ans[i]);
}
puts("");
}
return 0;
}
小结：toposort是一种处理存在先决条件问题或上下级关系的主要手段之一，它在一般情况下作为一个辅助的条件。比如我们可以维护一个appear数组表示一个数是否出现过从而达到判环的效果(NOI2009植物大战僵尸)，我们也可以通过拓扑排序来处理一些比较容易用图来表达的问题(没有上司的舞会)
查看9道真题和解析
