A graph which is connected and acyclic can be considered a tree. The height of the tree depends on the selected root. Now you are supposed to find the root that results in a highest tree. Such a root is called the deepest root.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (<=10000) which is the number of nodes, and hence the nodes are numbered from 1 to N. Then N-1 lines follow, each describes an edge by given the two adjacent nodes’ numbers.
Output Specification:
For each test case, print each of the deepest roots in a line. If such a root is not unique, print them in increasing order of their numbers. In case that the given graph is not a tree, print “Error: K components” where K is the number of connected components in the graph.
Sample Input 1:
|
1 2 3 4 5 |
5 1 2 1 3 1 4 2 5 |
Sample Output 1:
|
1 2 3 |
3 4 5 |
Sample Input 2:
|
1 2 3 4 5 |
5 1 3 1 4 2 5 3 4 |
Sample Output 2:
|
1 |
Error: 2 components |
这道题乍一看略微有点烦，实际比较简单。
写了一个只能针对这道题的比较 low 的解法，没有通用性，（毕竟题目要求比较特殊）。首先，可以该无向图知道有 N 个节点和 N-1 条边，那么就可以通过并查集来判断共有多少个连通集。然后以每个节点为起点，进行深度优先搜索，记录最高的节点信息即可。
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
#include<stdio.h> #include<stdlib.h> #include<memory.h> typedef struct list_ { int id; struct list_ *next; } list; typedef struct vertex_ { list *adjacent; } vertex; int set_found(int *set,int index) { int root,temp; temp=index; while(set[temp]>-1) { temp=set[temp]; } root=temp; temp=index; while(set[temp]>-1) { index=temp; temp=set[temp]; set[index]=root; } return root; } int set_union(int *set,int a,int b) { a=set_found(set,a); b=set_found(set,b); if(a==b) { return 0; } if(set[a]<set[b]) { set[a]+=set[b]; set[b]=a; } else { set[b]+=set[a]; set[a]=b; } return 1; } int main() { int i,n,total,from,to,*node_no,*stack,top=-1,current,*record,max=0,offset=0,*set; vertex *node; list *temp; scanf("%d",&n); total=n; node=(vertex *)malloc((n+1)*sizeof(vertex)); node_no=(int *)malloc((n+1)*sizeof(int)); record=(int *)malloc(n*sizeof(int)); stack=(int *)malloc(n*sizeof(int)); set=(int *)malloc((n+1)*sizeof(int)); memset(set,0xFF,(n+1)*sizeof(int)); for(i=0;i<=n;i++) { node[i].adjacent=NULL; } for(i=0;i<n-1;i++) { scanf("%d%d",&from,&to); if(set_union(set,from,to)) { total--; } temp=(list *)malloc(sizeof(list)); temp->id=to; temp->next=node[from].adjacent; node[from].adjacent=temp; temp=(list *)malloc(sizeof(list)); temp->id=from; temp->next=node[to].adjacent; node[to].adjacent=temp; } if(total!=1) { printf("Error: %d components\n",total); return 0; } total=0; for(i=1;i<=n;i++) { max=0; memset(node_no,0xFF,(n+1)*sizeof(int)); stack[++top]=i; node_no[i]=1; while(top>-1) { current=stack[top--]; temp=node[current].adjacent; if(node_no[current]>max) { max=node_no[current]; } while(temp!=NULL) { if(node_no[temp->id]==-1) { node_no[temp->id]=node_no[current]+1; stack[++top]=temp->id; } temp=temp->next; } } if(total<max) { total=max; offset=0; } if(max==total) { record[offset++]=i; } } for(i=0;i<offset;i++) { printf("%d\n",record[i]); } } |