1021 Deepest Root (25 分)（C语言实现）（PAT)

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 (≤10^​4​​ ) 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

算法&程序

#include <stdlib.h>
#include <stdio.h>
#define MaxSize 10001
typedef struct AdjNode *ptrToAdj;
struct AdjNode{
    int weight, index;
    ptrToAdj next;
};
typedef struct GNode *LGraph;
struct GNode{
    ptrToAdj G[MaxSize];
    int Ne, Nv;
};
LGraph build(int N)
{
    LGraph Graph = (LGraph)malloc(sizeof(struct GNode));
    Graph->Nv = N;
    Graph->Ne = N-1;
    for(int i = 1; i <= Graph->Nv; i++) Graph->G[i] = NULL;
    for(int i = 0; i < N-1; i++){
        int tmp1, tmp2;
        scanf("%d%d", &tmp1, &tmp2);
        ptrToAdj p;
        p = (ptrToAdj)malloc(sizeof(struct AdjNode));
        p->weight = 1;
        p->index = tmp1;
        p->next = Graph->G[tmp2];
        Graph->G[tmp2] = p;
        p = (ptrToAdj)malloc(sizeof(struct AdjNode));
        p->weight = 1;
        p->index = tmp2;
        p->next = Graph->G[tmp1];
        Graph->G[tmp1] = p;
    }
    return Graph;
}
int visited[MaxSize], cnt[MaxSize];
void DFS(LGraph Graph, int V)
{
    ptrToAdj W;
    visited[V] = 1;

    for(W = Graph->G[V]; W; W = W->next){
        if(!visited[W->index]){
            cnt[W->index] = cnt[V] + 1;
            DFS(Graph, W->index);
        }
    }
}

int deep(int n, int arr[])
{
    int max = 0;
    for(int i = 1; i <= n; i++){
        if(arr[i] > max) max = arr[i];
    }
    return max;
}
int main()
{
    int N,depth[MaxSize],c = 1,deepest;
    scanf("%d", &N);
    LGraph Graph = build(N);
    for(int i = 1; i <= N; i++ ){
        for(int j = 1; j <= N; j++){
            visited[j] = 0;
            cnt[j] = -1;
        }
        cnt[i] = 0;
        DFS(Graph, i);
        for(int j = 1; j <= N; j++){
            if(!visited[j]){
                DFS(Graph, j);
                c++;
            }
        }
        if(c == 1) depth[i] = deep(Graph->Nv,cnt);
        else break;
    }
    if(c != 1) printf("Error: %d components\n",c);
    else{
        deepest = deep(Graph->Nv,depth);
        for(int i = 1; i <= N; i++ ){
            if(depth[i] == deepest) printf("%d\n",i);
        }
    }
    return 0;
}