首页 > 代码库 > soj 1034 Forest_求树的深度和宽度
soj 1034 Forest_求树的深度和宽度
题目链接
题意:给你n个节点,m条边,每条边是有向的,这颗树不能有自环,问这颗树的深度和宽度
思路:
不合法情况
1,入度大于1,即存在两条指向同一顶点的边
2,一条入点和出点都相同的边
3,一条变得入点和出点深度已知,但不符合出点的深度是入点的深度加1
4,点入深度未知但出点深度已知
5,遍历完以后,有顶点未遍历,说明有多个根
树的宽度是指,同一层最多有多少个节点
#include <iostream> #include<cstdio> #include<cstring> using namespace std; #define MAXN 110 int n,m,edge[MAXN][2],indegree[MAXN],level[MAXN]; int main(int argc, char** argv) { int i,j,ok,doit,a,b; while(scanf("%d%d",&n,&m)!=EOF,n){ ok=1; for(i=0;i<=n;i++){ indegree[i]=0; level[i]=-1; } for(i=1;i<=m;i++){ scanf("%d%d",&a,&b); if(a==b) ok=0; edge[i][0]=a; edge[i][1]=b; indegree[b]++; if(indegree[b]>1) ok=0; } for(i=1;i<=n;i++) if(!indegree[i]) level[i]=0; doit=1; while(doit&&ok){ doit=0; for(i=1;i<=m;i++){ a=edge[i][0]; b=edge[i][1]; if(level[a]>=0){ if(level[b]>=0){ if(level[a]+1!=level[b]){ ok=0; break; } }else{ level[b]=level[a]+1; doit=1; } }else{ if(level[b]>=0) { ok=0; break; } } } } for(i=1;i<=n;i++) if(level[i]<0) ok=0; if(!ok){ printf("INVALID\n"); continue; } int depth=-1,width=-1,sum[110]; memset(sum,0,sizeof(sum)); for(i=1;i<=n;i++){ if(level[i]>depth)depth=level[i]; sum[level[i]]++; if(sum[level[i]]>width) width=sum[level[i]]; } printf("%d %d\n",depth,width); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。