ファミリーツリートポロジーアルゴリズム
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を最後に、世代の高い先を輸出する.トポロジーソートアルゴリズム
【入力形式】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;
}