频道栏目
首页 > 程序开发 > 软件开发 > Java > 正文
sdut3045迷之图论--(多叉树求最长链)
2014-12-12 11:24:33         来源:随风的专栏  
收藏   我要投稿


迷之图论

Time Limit: 1000MS Memory limit: 65536K

题目描述

FF是图论高手,所以我要出图论且不出流问题。

给出一个树,求树的最长链的长度。

输入

多组输入。每组输入的第一行为n(1 <= n <= 100000),代表节点个数,节点编号从1 到n,接下来的n-1行,每行两个正整数u,v,代表u,v之间有一条边相连。保证每组数据都是一棵树。

输出

对于每组数据,输出一个正整数代表答案。

示例输入

121 2

示例输出

12

提示

来源

zmx dfs搜索
#include 
#include 
#include 
using namespace std ;
struct node{
    int v ;
    int next ;
}p[1000000];
int head[110000] , cnt , vis[110000] ;
int ans , max1[110000] ;
void add(int u,int v)
{
    p[cnt].v = v ;
    p[cnt].next = head[u] ; head[u] = cnt++ ;
    p[cnt].v = u ;
    p[cnt].next = head[v] ; head[v] = cnt++ ;
}
void dfs(int u,int num)
{
    int i , j , v , flag = 0 , k1 = -1 , k2 = -1 ;
    for(i = head[u] ; i != -1 ; i = p[i].next)
    {
        v = p[i].v ;
        if( !vis[v] )
        {
            flag = 1 ;
            vis[v] = num+1 ;
            dfs(v,num+1) ;
        }
    }
    if( flag == 0 )
    {
        max1[u] = 1 ;
        return ;
    }
    for(i = head[u] ; i != -1 ; i = p[i].next)
    {
        v = p[i].v ;
        if( vis[u]+1 != vis[v] )
            continue ;
        if( k1 == -1 )
            k1 = max1[v] ;
        else
        {
            if( max1[v] > k1 )
            {
                k2 = k1 ;
                k1 = max1[v] ;
            }
            else if(  max1[v] > k2 )
                k2 = max1[v] ;
        }
    }
    max1[u] = k1 + 1 ;
    ans = max( ans,max1[u] ) ;
    if( k2 == -1 )
        return ;
    else
    {
        ans = max( ans,k1+k2+1 ) ;
    }
    return ;
}
int main()
{
    int n , u , v , i ;
    while( scanf("%d", &n) != EOF )
    {
        cnt = 0 ;
        ans = 2 ;
        memset(head,-1,sizeof(head)) ;
        memset(vis,0,sizeof(vis)) ;
        if(n == 1)
        {
            printf("1\n") ;
            continue ;
        }
        for(i = 1 ; i < n ; i++)
        {
            scanf("%d %d", &u, &v) ;
            add(u,v) ;
        }
        vis[1] = 1 ;
        dfs(1,1);
        printf("%d\n", ans) ;
    }
    return 0;
}


点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:12-11java面向对象之内部类操作
下一篇:Java基础知识陷阱(七)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站