首页 > 代码库 > POJ 2367 Genealogical tree 拓扑题解

POJ 2367 Genealogical tree 拓扑题解

一条标准的拓扑题解。


我这里的做法就是:

保存单亲节点作为邻接表的邻接点,这样就很方便可以查找到那些点是没有单亲的节点,那么就可以输出该节点了。


具体实现的方法有很多种的,比如记录每个节点的入度,输出一个节点之后,把这个节点对于其他节点的入度去掉,然后继续查找入度为零的点输出。这个是一般的做法了,效果和我的程序一样的。


有兴趣的也可以参考下我这种做法。


#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;

const int MAX_N = 101;
int N, v;
vector<int> gra[MAX_N];
bool vis[MAX_N];

void topologicalSort()
{
	int c = 0;
	while (c < N)
	{
		for (int i = 1; i <= N; i++)
		{
			if (vis[i]) continue;
			bool ind = 0;
			for (int j = 0; j < (int)gra[i].size(); j++)
			{
				if (!vis[gra[i][j]])
				{
					ind = true;
					break;
				}
			}
			if (!ind)
			{
				c++;
				vis[i] = true;
				printf("%d ", i);
			}
		}
	}

}

int main()
{
	while (~scanf("%d", &N))
	{
		for (int i = 1; i <= N; i++) gra[i].clear();
		memset(vis, 0, sizeof(vis));

		for (int u = 1; u <= N; u++)
		{
			while (~scanf("%d", &v) && v)
				gra[v].push_back(u);
		}
		topologicalSort();
		putchar('\n');
	}
	return 0;
}