1021. Deepest Root (25)

最新推荐文章于 2024-10-11 16:39:47 发布

puppet_pyt

最新推荐文章于 2024-10-11 16:39:47 发布

阅读量252

点赞数

分类专栏： pat甲级

本文链接：https://blog.csdn.net/puppet_pyt/article/details/70175094

版权

pat甲级专栏收录该内容

55 篇文章

订阅专栏

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:

Sample Output 1:

3
4
5

Sample Input 2:

Sample Output 2:

Error: 2 components

对每个点用BFS求出他的最长路径，效率很低不过还是过了，网上还有2次DFS就可以得出结果，还没有仔细看过，有时间再研究一下

/***并查集求集合数量***/
/****BFS求最长路径***/
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <cstring>
#define MAX 10005
using namespace std;

vector<int> graph[MAX];
bool visit[MAX];
int maxlen[MAX];//记录每个点最大深度
int pre[MAX] = {0};
int maxh = 0;//记录最大深度

int Find(int x)
{
    return pre[x]==x ? x : pre[x]=Find(pre[x]);
}

void Union(int x, int y)
{
    int u = Find(x);
    int v = Find(y);
    if(u == v)
        return ;
    pre[u] = v;
}

int bfs(int x)
{
    int len = 0;
    int dist[MAX] = {0};
    queue<int> myque;
    myque.push(x);
    visit[x] = true;
    while(!myque.empty())
    {
        x = myque.front();
        myque.pop();
        visit[x] = true;
        for(vector<int>::size_type i=0; i<graph[x].size(); i++)
        {
            if(!visit[graph[x][i]])
            {
                dist[graph[x][i]] = dist[x]+1;
                if(len < dist[graph[x][i]])
                    len = dist[graph[x][i]];
                myque.push(graph[x][i]);
            }
        }
    }
    if(len > maxh)
        maxh = len;
    return len;
}
int main()
{
    int n, x, y;
    int maxl = -1;
    int counter = 0;
    cin >> n;
    for(int i=0; i<=n; i++)
        pre[i] = i;
    for(int i=0; i<n-1; i++)
    {
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
        Union(x, y);
    }
    for(int i=1; i<=n; i++)
    {
        if(pre[i] == i)
            counter++;
    }
    if(counter > 1)
        cout << "Error: " << counter <<" components" << endl;
    else
    {
        for(int i=1; i<=n; i++)
        {
            memset(visit, false, sizeof(bool)*(n+1));
            maxlen[i] = bfs(i);
        }
        for(int i=1; i<=n; i++)
        {
            if(maxlen[i] == maxh)
                cout << i << endl;
        }
    }
    return 0;
}