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
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 01 11 13 11 32 21 22 10 88
Sample Output
0 1INVALID1 2INVALID
分析：
本题要求森林的深度和宽度，建议用深搜，因为广搜的循环控制条件很难写，极易出错或者死循环。要注意图生成的森林中，可能会出现公共子节点以及环等不合法情况，要注意判断条件。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#include using namespace std;#define N 101#define M 101bool 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 > 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;}