Description Last years Chicago was full of gangster fights and strange murders. The chief of the police got really tired of all these crimes, and decided to arrest the mafia leaders.
Unfortunately, the structure of Chicago mafia is rather complicated. There are n persons known to be related to mafia. The police have traced their activity for some time, and know that some of them are communicating with each other. Based on the data collected, the chief of the police suggests that the mafia hierarchy can be rePResented as a tree. The head of the mafia, Godfather, is the root of the tree, and if some person is represented by a node in the tree, its direct subordinates are represented by the children of that node. For the purpose of conspiracy the gangsters only communicate with their direct subordinates and their direct master.
Unfortunately, though the police know gangsters’ communications, they do not know who is a master in any pair of communicating persons. Thus they only have an undirected tree of communications, and do not know who Godfather is.
Based on the idea that Godfather wants to have the most possible control over mafia, the chief of the police has made a suggestion that Godfather is such a person that after deleting it from the communications tree the size of the largest remaining connected component is as small as possible. Help the police to find all potential Godfathers and they will arrest them.
Input The first line of the input file contains n — the number of persons suspected to belong to mafia (2 ≤ n ≤ 50 000). Let them be numbered from 1 to n.
The following n ? 1 lines contain two integer numbers each. The pair ai, bi means that the gangster ai has communicated with the gangster bi. It is guaranteed that the gangsters’ communications form a tree.
Output Print the numbers of all persons that are suspected to be Godfather. The numbers must be printed in the increasing order, separated by spaces.
Sample Input 6 1 2 2 3 2 5 3 4 3 6 Sample Output 2 3 問題概述 第一行輸入n表示一共有n個人，接下來的n-1行輸入相互交談的兩個人，這兩個人的上下級關(guān)系未知。已知每一個人之和和他的直接下屬和直接上司交談，下屬可以有多個，上司只有一個。而且已知，可以將他們的關(guān)系看成一棵樹，Godfather是這樣一個節(jié)點，把它從樹上刪除后剩余子樹的最大值要盡可能小。 問題分析 首先介紹一下經(jīng)常會用到的鄰接表的建立，來存儲一棵樹。
#define maxn 50002struct nod{ int v;//某個父親節(jié)點的孩子節(jié)點 int next;//指向下一個兄弟節(jié)點};nod e[2*maxn];//按照0，1，2。。。n的順序存儲nodint head[maxn];//表頭int e_size;//按照0，1，2。。。n的順序遞增void addEdge(int v,int u){ e[e_size].v=u; e[e_size].next=head[v];//新增孩子節(jié)點 head[v]=e_size++;//改變表頭的指向}//新增一個鏈表的節(jié)點，存入到e[e_size]中，并指向鏈表的第一個節(jié)點再用表頭指向該節(jié)點，就這樣插入到表頭和第一個節(jié)點之間成為頭節(jié)點。
接下來介紹具體的計算過程： 首先廣度優(yōu)先遍歷整棵樹，計算以每一個節(jié)點為根節(jié)點所在樹的大小num_Node[i]。 再次廣度優(yōu)先遍歷整棵樹，計算刪除當前節(jié)點后剩余的連接部分的大小，取最大值del_Node[i]。 設(shè)i_j為i的孩子節(jié)點，del_Node[i]=max(num_Node[i_j],n-num_Node[i]); i_j=i_1,i_2,i_3,,,,,,i_n; 最后取最大值的最小值。 result=min(del_Node[i]);i=1,2,3,,,,,n; 代碼實現(xiàn)
#include<iostream>#include<cstdio>#include<algorithm>using namespace std;#define maxn 50002struct nod{ int v; int next;};nod e[2*maxn];int head[maxn];int e_size;int num_Node[maxn];int del_Node[maxn];int bfs(int root,int father,int n){ int sum=0; int temp; int maxi=-1; for(int j=head[root];j!=-1;j=e[j].next) if(e[j].v!=father){ temp=bfs(e[j].v,root,n); sum+=temp; if(temp>maxi)maxi=temp; } num_Node[root]=sum+1; del_Node[root]=max(maxi,n-num_Node[root]); return num_Node[root];}void addEdge(int v,int u){ e[e_size].v=u; e[e_size].next=head[v]; head[v]=e_size++;}int main(){ int n; scanf("%d",&n); for(int i=1;i<n+1;i++){ head[i]=-1; num_Node[i]=0; del_Node[i]=0; } e_size=0; int v,u; for(int i=1;i<n;i++){ scanf("%d %d",&v,&u); addEdge(v,u); addEdge(u,v); } bfs(1,-1,n); int min=n+1; for(int i=1;i<n+1;i++) if(del_Node[i]<min)min=del_Node[i]; bool first=true; for(int i=1;i<n+1;i++) if(del_Node[i]==min){ if(first){first=false;printf("%d",i);} else printf(" %d",i); } printf("/n"); return 0;}新聞熱點
疑難解答
