首页 > 代码库 > sdut3045迷之图论--(多叉树求最长链)
sdut3045迷之图论--(多叉树求最长链)
迷之图论
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 <cstdio>#include <cstring>#include <algorithm>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;}
sdut3045迷之图论--(多叉树求最长链)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。