pat题目求解
本帖最后由 SCRCLS 于 2012-10-22 17:59:12 编辑 1021. Deepest Root (25)

时间限制
1500 ms
内存限制
32000 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue
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:
5
1 2
1 3
1 4
2 5
Sample Output 1:
3
4
5
Sample Input 2:
5
1 3
1 4
2 5
3 4
Sample Output 2:
Error: 2 components




http://pat.zju.edu.cn/contests/pat-practise/1021
1021. Deepest Root (25)

pat的一个题目，前面的csae过不了，想不明白哪里出错，求指教，谢谢

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node
{
int data;
struct node *next;
}Node, *Ver;//节点

typedef struct 
{
int v, e;
Ver *s;//头结点数组
}Graph;//邻接表表示图

typedef struct 
{
int num;
int data;
}Deep;

int visit[MAX];
Deep deep[MAX];

void Init(Graph *G)//初始化图
{
int i;
int s, e;
Node *temp;

scanf("%d", &G->v);

G->e = G->v - 1;
G->s = (Ver *)malloc(sizeof(Ver) * G->v);

for (i = 0; i < G->v; i++)
{
G->s[i] = (Node *)malloc(sizeof(Node));
G->s[i]->next = NULL;
G->s[i]->data = 0;
}

for (i = 0; i < G->e; i++)//无向图
{
scanf("%d%d", &s, &e);

s -= 1;
e -= 1;

temp = (Node *)malloc(sizeof(Node));
temp->data = e;
temp->next = G->s[s]->next;
G->s[s]->next = temp;

temp = (Node *)malloc(sizeof(Node));
temp->data = s;
temp->next = G->s[e]->next; 
 
G->s[e]->next = temp;
}
}

int cmp(const void *a, const void *b)//快排的cmp
{
Deep *c = (Deep *)a;
Deep *d = (Deep *)b;

if (c->data != d->data)//按照高度降序
return d->data - c->data;
else //如果高度想同，那么按照序号升序
return c->num - d->num;
}

void Clear(int len)//清空visit
{
memset(visit, 0, sizeof(int) * (len + 1));
}

void DFS(Graph G, int start, int *high)//深度搜索
{
int v;
int flag = 0;
Node *temp;

visit[start] = 1;

temp = G.s[start]->next;
while (temp)
{
v = temp->data;
if (!visit[v])
{
if (flag == 0)
{
*high += 1;
flag = 1;//已到过该层
}
DFS(G, v, high);
}
temp = temp->next;
}
}

void DFSVisit(Graph G)
{
int i, j = 0;
int high = 1, count = 0;
int max;

Clear(G.v);

for (i = 0; i < G.v; i++)//判断是否强连通
if (!visit[i])
{
DFS(G, i, &high);
count++;
}
if (count > 1)
printf("Error: %d components\n", count);
else //强连通
{
for (i = 0; i < G.v; i++)//逐个找出每个节点的deepest tree high
{
Clear(G.v);
high = 1;
DFS(G, i, &high);
deep[j].num = i + 1;
deep[j++].data = high;
}
qsort(deep, j, sizeof(Deep), cmp);//排序

max = deep[0].data;

for (i = 0; i < j && deep[i].data == max; i++)//输出节点
{
printf("%d\n", deep[i].num);
}

}

}


int main()
{
Graph G;

Init(&G);
DFSVisit(G);
return 0;
}