文档章节

sicily 1034 Forest

Ciel
 Ciel
发布于 2012/12/17 21:03
字数 686
阅读 76
收藏 0

Description

In the field of computer science, forest is important and deeply researched , it is a model for many data structures . Now it’s your job here to calculate the depth and width of given forests.

     Precisely, a forest here is a directed graph with neither loop nor two edges pointing to the same node. Nodes with no edge pointing to are roots, we define that roots are at level 0 . If there’s an edge points from node A to node B , then node B is called a child of node A , and we define that B is at level (k+1) if and only if A is at level k .

      We define the depth of a forest is the maximum level number of all the nodes , the width of a forest is the maximum number of nodes at the same level.

Input

There’re several test cases. For each case, in the first line there are two integer numbers n and m (1≤n≤100, 0≤m≤100, m≤n*n) indicating the number of nodes and edges respectively , then m lines followed , for each line of these m lines there are two integer numbers a and b (1≤a,b≤n)indicating there’s an edge pointing from a to b. Nodes are represented by numbers between 1 and n .n=0 indicates end of input.

Output

For each case output one line of answer , if it’s not a forest , i.e. there’s at least one loop or two edges pointing to the same node, output “INVALID”(without quotation mark), otherwise output the depth and width of the forest, separated by a white space.

Sample Input

1 0
1 1
1 1
3 1
1 3
2 2
1 2
2 1
0 88

Sample Output

0 1
INVALID
1 2
INVALID

分析:

本题要求森林的深度和宽度,建议用深搜,因为广搜的循环控制条件很难写,极易出错或者死循环。要注意图生成的森林中,可能会出现公共子节点以及环等不合法情况,要注意判断条件。DFS过程中遇到了已经访问过的节点说明有公共子节点的存在,DFS完成后仍有节点未被访问说明有环存在。另外,一次完整的DFS过程中求得的广度只是一棵树的广度,要对同一深度的节点全部统计才能得到森林的广度。

代码:

// Problem#: 1034
// Submission#: 1795986
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
#include <iostream>
#include <cstring>
using namespace std;

#define N 101
#define M 101

bool flag;
bool buffer[N][N];
bool visit[N];
bool isroot[N];
int maxd,n,m,maxb;
int b[N];

void dfs( int p, int td ){
    if( visit[p] ){
        flag = false;
        return ;
    }
    visit[p] = true;
    maxd = td>maxd ? td : maxd;
    if(++b[td]>maxb) maxb = b[td];
    for( int i=1 ; i<=n ; i++ ){
        if( buffer[p][i] ){
            if(!flag) return ;
            dfs(i,td+1);
        }else
            continue;
    }
}

int main(){
    int x,y;
    while( cin>>n>>m && n ){
        memset(buffer,0,sizeof(buffer));
        memset(visit,0,sizeof(visit));
        memset(isroot,true,sizeof(isroot));
        flag = true;
        if(m>=n) flag = false;
        for( int i=0 ; i<m ; i++ ){
            cin >> x >> y;
            buffer[x][y] = true;
            isroot[y] = false;
        }
        maxd = maxb = 0;
        memset(b,0,sizeof(b));
        for( int i=1 ; i<=n ; i++ )
            if( isroot[i] ) dfs(i,0);
        for( int i=1 ; i<=n ; i++ ){
            if( !visit[i] ){
                flag = false;
                break;
            }
        }
        if( flag ) cout << maxd << " " << maxb;
        else cout << "INVALID";
        cout << endl;
    }
    return 0;
}

© 著作权归作者所有

Ciel
粉丝 3
博文 24
码字总数 18532
作品 0
程序员
私信 提问
Oracle 11g R2 ADG 搭建

--============Oracle ADG搭建============== --==========准备阶段========= 1.检查primary为archivelog模式。 select log_mode from v$database; 如果为noarchivelog模式,切换到archivelo......

UltraSQL
2018/07/23
0
0
oracle查询数据重复

SQL 1: select t4.pre_operaction_id from T_CT_LINK_OPER_EXE_CONDITION t4 left join T_CT_REF_LINK_OPERACTION t5 on t4.link_operaction_id = t5.link_operaction_id where t5.link_id =......

北方蛮子
2013/01/08
489
2
Adobe Illustrator 各个版本注册码 序列号 破解补丁 下载地址专题

介绍:Adobe Illustrator介绍: Adobe illustrator作为全球最著名的矢量图形软件,以其强大的功能和体贴用户的界面,已经占据了全球矢量编辑软件中的大部分份额。据不完全统计全球有37%的设计...

江哥一直在
2016/01/11
10.6K
0
PHP实现微信开放平台扫码登录源码下载

演示下载地址: http://www.erdangjiade.com/php/1034.html 1、首先到微信开放平台申请https://open.weixin.qq.com/ 获取到appid和APPSECRET,前台显示页面如下 2、PHP处理代码页面 演示下载...

2当家的
2017/02/06
1K
0
随机森林入门

Random forest is a highly versatile machine learning method with numerous applications ranging from marketing to healthcare and insurance. It can be used to model the impact of ......

AC-carrot
2016/06/03
105
0

没有更多内容

加载失败,请刷新页面

加载更多

js如何控制table中的某一行动态置顶

两行代码搞定: $('#'+item.roadCode).fadeOut().fadeIn();//获取到需要置顶的行 $(".table").prepend($('#'+item.roadCode)); 其中,fadeOut()方法 作用 --- 从可见到隐藏 如下: prepend(......

码妞
今天
4
0
四种解决Nginx出现403 forbidden 报错的方法

我是在在本地用虚拟机中通过yum安装nginx的,安装一切正常,但是访问时报403, 于是查看nginx日志,路径为/var/log/nginx/error.log。打开日志发现报错Permission denied,详细报错如下: 1....

dragon_tech
今天
3
0
获取RestResultResponse返回的值

Springboot项目,需要调其他服务的接口,返回值类型是RestResultResponse 打断点的结果集是这个 打印出来的getData(): [{id=3336b624-8474-4dd9-bd5b-c7358687c877, paraNo=104, para=Postpo...

栾小糖
今天
4
0
【小学】 生成10以内的加减法

#!/usr/bin/env python# coding: utf-8from random import randrange# 题目的最大数值R_MAX = 10# 生成的题目的数量R_PAGE = 70# 生成减法列表def get_sub_list():...

Tensor丨思悟
今天
11
0
JavaScript设计模式——适配器模式

  适配器模式是设计模式行为型模式中的一种模式;   定义:   适配器用来解决两个已有接口之间不匹配的问题,它并不需要考虑接口是如何实现,也不用考虑将来该如何修改;适配器不需要修...

有梦想的咸鱼前端
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部