Adjoin the Networks Gym - 100781A

　

adjoin

http://codeforces.com/gym/100781/attachments

给出一个森林 问将图连通后最小的树直径

对于所有连通块都求出直径 若只有一个连通块则直接输出 有两个则比较一下最大直径以及最大最小折半相连后的直径 取个最小值 因为将两棵树连在一起肯定是连两者重心

若多于两个 则用所有重心连一个星形图 为了让树的高度尽可能小 这时次大和次次大的直径的重心之间连边数为2 此处也可能会产生直径

#include <bits/stdc++.h>
using namespace std;

struct node1
{
    int u;
    int v;
};

struct node2
{
    int v;
    int next;
};

node1 pre[100010];
node2 edge[200010];
int f[100010],first[100010],dis[100010],len[100010];
int n,m,num;

void addedge(int u,int v)
{
    edge[num].v=v;
    edge[num].next=first[u];
    first[u]=num++;
}

int getf(int p)
{
    if(f[p]==p) return p;
    else
    {
        f[p]=getf(f[p]);
        return f[p];
    }
}

void unite(int u,int v)
{
    int fu,fv;
    fu=getf(u),fv=getf(v);
    f[fv]=fu;
}

void dfs(int cur,int fa,int &p)
{
    int i,v;
    for(i=first[cur];i!=-1;i=edge[i].next)
    {
        v=edge[i].v;
        if(v!=fa)
        {
            dis[v]=dis[cur]+1;
            if(dis[p]<dis[v]) p=v;
            dfs(v,cur,p);
        }
    }
}

int main()
{
    int i,p1,p2;
    scanf("%d%d",&n,&m);
    memset(first,-1,sizeof(first));
    num=0;
    for(i=1;i<=n;i++) f[i]=i;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&pre[i].u,&pre[i].v);
        pre[i].u++,pre[i].v++;
        addedge(pre[i].u,pre[i].v);
        addedge(pre[i].v,pre[i].u);
        unite(pre[i].u,pre[i].v);
    }
    num=0;
    for(i=1;i<=n;i++)
    {
        if(f[i]==i)
        {
            dis[i]=0,p1=i;
            dfs(i,0,p1);
            dis[p1]=0,p2=i;
            dfs(p1,0,p2);
            len[++num]=dis[p2];
        }
    }
    sort(len+1,len+num+1);
    if(num==1) printf("%d\n",len[1]);
    else if(num==2) printf("%d\n",max(len[num],(len[num-1]+1)/2+(len[num]+1)/2+1));
    else printf("%d\n",max(len[num],max((len[num-1]+1)/2+(len[num]+1)/2+1,(len[num-2]+1)/2+(len[num-1]+1)/2+2)));
    return 0;
}

相关阅读