poj 2367 Genealogical tree （拓扑排序）-程序员宅基地

火星人的血缘关系很奇怪，一个人可以有很多父亲，当然一个人也可以有很多孩子。
有些时候分不清辈分会产生一些尴尬。所以写个程序来让n个人排序，长辈排在晚辈前面。

输入：N 代表n个人 1~n 接下来n行 第i行表示第i个人的孩纸，无序排列，可能为空。0代表一行输入结束。

（大概我的智商真的不合适，否则怎么这么久了连个拓扑排序都写不好，T了三次。。）

代码：

/********************************************
Problem: 2367		User:
Memory: 700K		Time: 32MS
Language: G++		Result: Accepted
********************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int N = 105;
int n;
vector<int> G[N];
int RD[N];
int vis[N];

void topsort()
{
	for (int j = 1; j <= n; ++j)
		for (int i = 1; i <= n; ++i) {
			if (!vis[i] && RD[i] == 0) {

				if (j != 1) printf(" ");
				printf("%d", i);
				for (int k = 0; k < G[i].size(); ++k)
					--RD[G[i][k]];
				vis[i] = 1;
				break;
			}
		}
	printf("\n");
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		int temp;
		while (scanf("%d", &temp) == 1) {
			if (temp == 0) break;
			G[i].push_back(temp);
			++RD[temp];
		}
	}
	topsort();
    return 0;
}

　　

好吧，改了一下第一次的代码也A了，输入的问题= =#

/****************************************
Problem: 2367		User: 
Memory: 736K		Time: 0MS
Language: G++		Result: Accepted
****************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int N = 105;

int mp[N][N]; // mp[i][j] i is j's son
int vis[N];
int n;

void read(int i)
{
	char ch;
	int ans = 0;
	
	while (scanf("%d", &ch), ch) {
		mp[ch][i] = 1;
		++mp[ch][0];
	}
}

void tpsort()
{
	int i, j;
	for (j = 1; j <= n; ++j) {
		for (i = 1; i <= n; ++i) {
			if (!vis[i] && mp[i][0] == 0) {
				if (j != 1) printf(" ");
				printf("%d", i);
				vis[i] = 1;

				for (int k = 1; k <= n; ++k) {
					if (!vis[k] && mp[k][i] == 1) {
						mp[k][i] = 0;
						--mp[k][0];
					}
				}
				break;
			}
		}
	}
	printf("\n");
}

int main()
{
    scanf("%d", &n);
	getchar();
	memset(mp, 0, sizeof mp);
	memset(vis, 0, sizeof vis);
	for (int i = 1; i <= n; ++i) {
		read(i);
	}
	tpsort();
    return 0;
}