[各種面接問題]木の最小高さ
2348 ワード
タイトルの説明:
無方向ツリーを指定すると、ルートノードとして異なるノードを選択すると、異なる高さ(すなわち、ルートノードからリーフノードまでの距離の最大値)が得られ、このツリーの可能な最低高さが求められます.
入力:
入力には、複数のテストケースが含まれる場合があります.各テストケースについて、入力された第1の動作は整数n(1<=n<=1000000)である.次のn−1行に続き、各行は2つの整数uを含み、v(0<=u、v出力:
各テストケースに対応して、このツリーの可能な最小高さを出力します.
サンプル入力:
サンプル出力:
グーグルのある年の筆記試験問題のような印象ですね.
私の考え方はこの図の中の最長の経路を求めて、それから明らかに最小の高さを得るならば、木の根はきっとこの最長の経路の中間ノードを根として、しかしこの最長の経路が奇数と偶数の処理であることに注意します.つまり、最後に1つのノードまたは2つのノードが残っている場合、1つのノードしか残っていない場合は、ルートですね.2つのノードであれば、2つのノードはルートとして使用でき、最後の高さは1つ追加します.
最长のパスを求めると、任意の点をルートとして探し(マルチフォークツリーはツリーではないことに注意してください)、これと同じように、エッジの重み値が1になります.
http://blog.csdn.net/a83610312/article/details/11786571つまり、この最長経路はある子供の中の最長経路か、ある子供から自分がリンクしている別の子供に行くかのどちらかです.
考え方はこのようにして、皆さんは興味があって自分でもう一度実現します.
そして他の人のDP解法をもう一つお勧めします.私自身もまだ理解していません..
http://t.jobdu.com/thread-101867-1-1.html
もう一つの素晴らしい方法はBFSを2回作ることです.http://eriol.iteye.com/blog/1171820
もう一つはトポロジーソートを利用してDPを作るのも巧みです.http://www.cnblogs.com/yanlingyin/archive/2011/11/12/2246716.html
無方向ツリーを指定すると、ルートノードとして異なるノードを選択すると、異なる高さ(すなわち、ルートノードからリーフノードまでの距離の最大値)が得られ、このツリーの可能な最低高さが求められます.
入力:
入力には、複数のテストケースが含まれる場合があります.各テストケースについて、入力された第1の動作は整数n(1<=n<=1000000)である.次のn−1行に続き、各行は2つの整数uを含み、v(0<=u、v
各テストケースに対応して、このツリーの可能な最小高さを出力します.
サンプル入力:
3
0 1
1 2
5
0 1
1 2
1 3
1 4サンプル出力:
1
1グーグルのある年の筆記試験問題のような印象ですね.
私の考え方はこの図の中の最長の経路を求めて、それから明らかに最小の高さを得るならば、木の根はきっとこの最長の経路の中間ノードを根として、しかしこの最長の経路が奇数と偶数の処理であることに注意します.つまり、最後に1つのノードまたは2つのノードが残っている場合、1つのノードしか残っていない場合は、ルートですね.2つのノードであれば、2つのノードはルートとして使用でき、最後の高さは1つ追加します.
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<climits>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
const int MAXN=1000005;
vector<int> adj[MAXN];
vector<int> indegree(MAXN);
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)
{
indegree[i]=0;
adj[i].clear();
}
for(int i=0;i<n-1;i++)
{
int a,b;
scanf("%d%d",&a,&b);
adj[a].push_back(b);
adj[b].push_back(a);
indegree[a]++;
indegree[b]++;
}
int cnt=n;
queue<int> Q;
for(int i=0;i<n;i++)
if(indegree[i]==1)
{
Q.push(i);
cnt--;
}
int len=0;
while(!Q.empty())
{
len++;
if(cnt<=2)
break;
int k=Q.size();
while(k--)
{
int t=Q.front();
Q.pop();
for(int i=0;i<adj[t].size();i++)
if(--indegree[adj[t][i]]==1)
{
Q.push(adj[t][i]);
cnt--;
}
}
}
if(cnt==1)
printf("%d
",len);
else
printf("%d
",len+1);
}
}最长のパスを求めると、任意の点をルートとして探し(マルチフォークツリーはツリーではないことに注意してください)、これと同じように、エッジの重み値が1になります.
http://blog.csdn.net/a83610312/article/details/11786571つまり、この最長経路はある子供の中の最長経路か、ある子供から自分がリンクしている別の子供に行くかのどちらかです.
考え方はこのようにして、皆さんは興味があって自分でもう一度実現します.
そして他の人のDP解法をもう一つお勧めします.私自身もまだ理解していません..
http://t.jobdu.com/thread-101867-1-1.html
もう一つの素晴らしい方法はBFSを2回作ることです.http://eriol.iteye.com/blog/1171820
もう一つはトポロジーソートを利用してDPを作るのも巧みです.http://www.cnblogs.com/yanlingyin/archive/2011/11/12/2246716.html