文章標(biāo)題

2019-11-08 02:10:54

字體：大中小

供稿：網(wǎng)友

/*法一：孩子節(jié)點(diǎn)用動(dòng)態(tài)數(shù)組，隊(duì)列中存的是完整的節(jié)點(diǎn)信息而非一個(gè)節(jié)點(diǎn)的序號(hào)，用數(shù)組存層數(shù)和該層孩子數(shù)。*/#include<iostream>#include<queue>#include<vector>//#PRagma warning(disable:4996)using namespace std;#define MAX 101 //常量的定義/*序號(hào)，層數(shù)，孩子個(gè)數(shù)，孩子數(shù)組，其中序號(hào)可用node數(shù)組下標(biāo)來(lái)表示*/struct node{ int level; vector<int> child;//動(dòng)態(tài)數(shù)組存孩子};int main(){ //freopen("input.txt","r",stdin); node tree[MAX]; int N,M; cin>>N>>M; for(int i=0;i<M;i++){ int index,k; cin>>index>>k; for(int j=0;j<k;j++){ int childId; cin>>childId; tree[index].child.push_back(childId); } } queue<node> q; int root=1; tree[root].level=1; q.push(tree[root]);//01號(hào)整個(gè)節(jié)點(diǎn)插入 int maxLevel=1,maxCount=0; int countLevel[MAX]={101};//下標(biāo)表示層數(shù)，下標(biāo)對(duì)應(yīng)的數(shù)組元素表示該層節(jié)點(diǎn)數(shù), while(!q.empty()){ //BFS廣度優(yōu)先用隊(duì)列 node curNode=q.front(); q.pop(); countLevel[curNode.level]++; if(countLevel[curNode.level]>maxCount){ maxCount=countLevel[curNode.level]; maxLevel=curNode.level; } for(int i=0;i<curNode.child.size();i++){ tree[curNode.child[i]].level=curNode.level+1; q.push(tree[curNode.child[i]]); } } cout<<maxCount<<" "<<maxLevel<<endl; return 0;}> http://blog.csdn.net/flx413/article/details/52641124/*法2：比法一low一些*/#include<iostream>#include<queue>//#pragma warning(disable:4996)using namespace std;#define MAX 101 //常量的定義/*序號(hào)，層數(shù)，孩子個(gè)數(shù)，孩子數(shù)組，其中序號(hào)可用node數(shù)組下標(biāo)來(lái)表示*/struct node{ int level; int k; int child[MAX];};int main(){ //freopen("input.txt","r",stdin); node tree[MAX]; int N,M;cin>>N>>M; for(int i=1;i<=N;i++){ //下標(biāo)從1開(kāi)始，下標(biāo)為節(jié)點(diǎn)序號(hào) tree[i].level=1; tree[i].k=0; } for(int i=0;i<M;i++){ int index;cin>>index;cin>>tree[index].k; for(int j=0;j<tree[index].k;j++){ cin>>tree[index].child[j]; } }/*在紙上畫(huà)一棵樹(shù)，有5個(gè)結(jié)點(diǎn).根是1，他的左孩子是3，右孩子是5，3的孩子是2，2的孩子是4按照下面這個(gè)執(zhí)行過(guò)程，就剛才箭頭指的那個(gè)位置開(kāi)始，1號(hào)結(jié)點(diǎn)是根結(jié)點(diǎn)，層是1他有兩個(gè)孩子分別是3和5，那么3和5的level是2，然后開(kāi)始訪問(wèn)2號(hào)結(jié)點(diǎn)了，2的孩子是4，但是此時(shí)2這個(gè)結(jié)點(diǎn)level還是1(初始化)，這個(gè)是錯(cuò)誤的. for(int i=1;i<=N;i++){ for(int j=0;j<tree[i].k;j++){ tree[tree[i].child[j]].level=tree[i].level+1; } }*/ queue<node> q; int root=1; tree[root].level=1; q.push(tree[root]);//01插入 int lev=1,cnt=0; //lev某層，cnt某層的葉子節(jié)點(diǎn)數(shù) int maxlev=1,maxcnt=0; while(!q.empty()){ //BFS廣度優(yōu)先用隊(duì)列 node curNode=q.front();q.pop(); int curlev=curNode.level; if(curlev!=lev){ if(cnt>maxcnt){ maxcnt=cnt; maxlev=lev; } cnt=0; lev=curlev; } cnt++; for(int i=0;i<curNode.k;i++){ tree[curNode.child[i]].level=curNode.level+1; q.push(tree[curNode.child[i]]); } } if(cnt>maxcnt){//考慮到如果最后一層是最多節(jié)點(diǎn)的情況 maxcnt=cnt; maxlev=lev; } cout<<maxcnt<<" "<<maxlev<<endl; return 0;}

上一篇：LeetCode -- First Unique Character in a String

下一篇：LeetCode -- Arranging Coins