URAL 1056 Computer Net （图论+bfs）

谁践踏了优雅 2022-06-04 03:55 151阅读 0赞

### Background ###

Computer net is created by consecutive computer plug-up to one that has already been connected to the net. Each new computer gets an ordinal number, but the protocol contains the number of its parent computer in the net. Thus, protocol consists of several numbers; the first of them is always 1, because the second computer can only be connected to the first one, the second number is 1 or 2 and so forth. The total quantity of numbers in the protocol is *N* − 1 ( *N* is a total number of computers). For instance, protocol 1, 1, 2, 2 corresponds to the following net:

The distance between the computers is the quantity of mutual connections (between each other) in chain. Thus, in example mentioned above the distance between computers \#4 and \#5 is 2, and between \#3 and \#5 is 3.

*Definition.* Let the center of the net be the computer which has a minimal distance to the most remote computer. In the shown example computers \#1 and \#2 are the centers of the net.

### Problem ###

Your task is to find all the centers using the set protocol.

Input

The first line of input contains an integer *N*, the quantity of computers (2 ≤ *N* ≤ 10000). Successive *N* − 1 lines contain protocol.

Output

Output should contain ordinal numbers of the determined net centers in ascending order.

Example

<table style="border-collapse:collapse; border:1px solid rgb(26,92,200)"> 
 <tbody> 
  <tr> 
   <th style="border:1px solid rgb(26,92,200); vertical-align:top; padding:3px; color:rgb(26,92,200)"> input</th> 
   <th style="border:1px solid rgb(26,92,200); vertical-align:top; padding:3px; color:rgb(26,92,200)"> output</th> 
  </tr> 
  <tr> 
   <td style="border:1px solid rgb(26,92,200); vertical-align:top; padding:3px"> <pre style="white-space:pre-wrap; word-wrap:break-word">5
1
1
2
2
</pre> </td> 
   <td style="border:1px solid rgb(26,92,200); vertical-align:top; padding:3px"> <pre style="white-space:pre-wrap; word-wrap:break-word">1 2
</pre> </td> 
  </tr> 
 </tbody> 
</table>

题解：

题意：

给一张有n-1条边的连通图，求与所有点中最大距离最小的点

思路：

先随便从一个点bfs求出最远的点tar1，然后从tar1开始bfs求出最远点记为tar2，记录下tar1和tar2的最大距离为len，同时记录各点到tar1的距离，然后再从tar2bfs一遍记录各点到tar2的距离，然后遍历所有点，满足dis1\[i\]+dis2\[i\]==len&&(dis1\[i\]==len/2||dis2\[i\]==len/2)的点为所求点，代码有点挫

代码：

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<queue>
    #include<stack>
    #include<math.h>
    #include<vector>
    #include<map>
    #include<set>
    #include<stdlib.h>
    #include<cmath>
    #include<string>
    #include<algorithm>
    #include<iostream>
    #include<stdio.h>
    using namespace std;
    vector<int>p[10005];
    int vis[10005];
    int tar1,tar2;
    struct node
    {
        int index;
        int step;
    };
    queue<node>q;
    int a[2][10005];
    int main()
    {
        int n,i,j,x,u,maxx,len;
        while(scanf("%d",&n)!=EOF)
        {
        for(i=2;i<=n;i++)
        {
            scanf("%d",&x);
            vis[i]=0;
            p[i].push_back(x);
            p[x].push_back(i);
        }
        maxx=0;
        node now,next;
        now.index=1;
        now.step=0;
        q.push(now);
        vis[1]=1;
        while(!q.empty())
        {
            now=q.front();
            if(now.step>maxx)
            {
                maxx=now.step;
                tar1=now.index;
            }
            q.pop();
            for(i=0;i<p[now.index].size();i++)
            {
                u=p[now.index][i];
                if(!vis[u])
                {
                    next.index=u;
                    next.step=now.step+1;
                    q.push(next);
                    vis[u]=1;
                }
            }
        }
        now.index=tar1;
        now.step=0;
        maxx=0;
        memset(vis,0,sizeof(vis));
        q.push(now);
        vis[tar1]=1;
        while(!q.empty())
        {
            now=q.front();
            if(now.step>maxx)
            {
                maxx=now.step;
                tar2=now.index;
            }
            a[0][now.index]=now.step;
            q.pop();
            for(i=0;i<p[now.index].size();i++)
            {
                u=p[now.index][i];
                if(!vis[u])
                {
                    next.index=u;
                    next.step=now.step+1;
                    q.push(next);
                    vis[u]=1;
                }
            }
        }
        len=maxx;
        now.index=tar2;
        now.step=0;
        memset(vis,0,sizeof(vis));
        q.push(now);
        vis[tar2]=1;
        while(!q.empty())
        {
            now=q.front();
            a[1][now.index]=now.step;
            q.pop();
            for(i=0;i<p[now.index].size();i++)
            {
                u=p[now.index][i];
                if(!vis[u])
                {
                    next.index=u;
                    next.step=now.step+1;
                    q.push(next);
                    vis[u]=1;
                }
            }
        }
        int c=len/2;
        int tag=0;
        //printf("tar1=%d tar2=%d\n",tar1,tar2);
        for(i=1;i<=n;i++)
        {
            if(a[0][i]+a[1][i]==len&&(a[0][i]==c||a[1][i]==c))
            {
                if(tag)
                    printf(" %d",i);
                else
                    printf("%d",i);
                tag=1;
            }
            p[i].clear();
        }
        printf("\n");
        }
        return 0;
    }