ファミリーツリートポロジーアルゴリズム

1188 ワード

【質問の説明】個人の家族が大きく、世代関係が混乱しているので、その関係を整理してください.一人一人の子供の情報を与えます.一人一人の後輩がその人より後ろにリストされるようにシーケンスを出力します.
【入力形式】1行目の整数N(1<=N<=100)は、家族の人数を表します.次に、N行目、I行目はI人目の息子を表します.各行の最後は0で説明が終わります.
【出力フォーマット】各人の後輩がその人よりも後にリストされるようにシーケンスを出力します.複数の解があれば任意の解を出力します.
【入力サンプル】
 5
 0 
 4 5 1 0
 1 0
 5 3 0 
3 0
【出力サンプル】2 4 5 3 1
标题:第i行為iの息子は、0を最後に、世代の高い先を輸出する.トポロジーソートアルゴリズム
#include
#include
using namespace std;
int r[101],c[101];
int a[101][101], ans[101];
int  num, tot, temp, n, j, i;
int main()
{
	cin >> n;
	for (i = 1; i <= n; i++)
	{
		do
		{
			cin >> j;
			if (j != 0)
			{
				c[i]++;//  i    
				a[i][c[i]] = j;
				r[j]++;// j    

			}

		} 
		while (j != 0);
	}
	for (i = 1; i <= n; i++)
	{
		if (r[i] == 0)
			ans[++tot] = i;//             ,        ans[]  
	}
	do
	{
		temp = ans[tot];
		cout << temp << " ";
		tot--; num++;
		for (i = 1; i <= c[temp]; i++)
		{
			r[a[temp][i]]--;
			if (r[a[temp][i] ]== 0)//         0,     
				ans[++tot] = a[temp][i];

		}
	} 
	while (num != n);//        n ,    
	system("pause");
	return 0;
}