小さい字の世代(c/c++)の本題は1つの巨大な家族の家譜を与えて、あなたに最小の世代のリストを与えてください.

入力形式:
最初の行に入力すると、家族の人口総数N(100,000を超えない正の整数)が与えられます.簡単に言えば、家族のメンバーを1からNまで番号付けします.次に、2行目には、i番目の番号がi番目のメンバーの親に対応するN個の番号が与えられる.家譜の中で最も上位の祖先に対応する父/母番号は-1である.1行の数値をスペースで区切ります.
出力フォーマット:
まず最小の世代を出力する(先祖の世代は1で、以下は段階的に増加する).次に、2行目に最小のメンバーを増分順に出力します.番号間は1つのスペースで区切られており、行の先頭と末尾に余分なスペースがないようにしてください.
サンプルを入力:
9 2 6 5 5 -1 5 6 4 7
出力サンプル:
4 1 9
...タイムアウトしました--私はまず再帰を使って、深さの検索を行いますが、そのテストのデータはとても大きくて、テストポイントを过ごすことができません.のこの問題はN個の親ノード(1から)を入力し,そのインデックス値(1から)がその子であることを意味する.こうして1本の木が形成され,最小のメンバーが木の最下層の葉ノードである.
私の考え:インデックス値が1からNなので、一人に対応して、重複していないので、普通の配列を使いました.配列のインデックスはこの人で、配列の値はその親世代です.ある親世代は−1(dfs関数に伝達され、dfs(−1))であり、それから再帰関数dfs(n)に入る.関数では、すべてのノードを巡回し、配列[i]=nの場合、次のレイヤ:dfs(i)に進みます.iの親はnで、nの子を見つけたという意味です.またiの子を探して・・・世代と番号を記録するなら、setを使います.よく考えてみると、それほど悪くない.
コードは次のとおりです(実行タイムアウト):

#include
#include
using namespace std;
int N;
int len;
int maxLen=-1;
int num[100000];
set s;
void dfs(int n){
	if(len>maxLen){
		maxLen=len;
		s.clear();
		s.insert(n);
	}else if(len==maxLen){
		s.insert(n);
	}
	for(int i=1;i<=N;i++){
		if(num[i]==n){
			len++;
			dfs(i);
			len--;
		}
	}
}
int main(){
	cin>>N;
	for(int i=1;i<=N;i++){
		cin>>num[i];
	}
	dfs(-1);
	cout<::iterator it = s.begin();it!=s.end();it++){
        if(it!=s.begin()){
            printf(" ");
        }
        printf("%d",*it);
    }
	return 0; 
}

そして、です...他人のコード.考え方は簡単で、最も重要なのは、タイムアウトしないことです.その配列はvector v,v[num]である.push_back(i);numは父の代、iは子の代.コードは次のとおりです.

#include
#include
#include
using namespace std;
int maxlevel = 1;
vector> v;
set s;
void dfs(int node,int level){
    if(level>maxlevel){
        maxlevel = level;
        s.clear();
        s.insert(node);
    }else if(level == maxlevel){
    s.insert(node);
    }
    for(int i=0;i::iterator it = s.begin();it!=s.end();it++){
        if(it!=s.begin()){
            printf(" ");
        }
        printf("%d",*it);
    }
    return 0;
}

Emmmm、早めにみんなの六一の楽しみを祈ります!(子供じゃないから)
強さと自信を一身に集めたシイタケの涼しさ.