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 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过程中求得的广度只是一棵树的广度,要对同一深度的节点全部统计才能得到森林的广度。
代码:
1 // Problem#: 1034 2 // Submission#: 1795986 3 // The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License 4 // URI: http://creativecommons.org/licenses/by-nc-sa/3.0/ 5 // All Copyright reserved by Informatic Lab of Sun Yat-sen University 6 #include <iostream> 7 #include <cstring> 8 using namespace std; 9 10 #define N 101 11 #define M 101 12 13 bool flag; 14 bool buffer[N][N]; 15 bool visit[N]; 16 bool isroot[N]; 17 int maxd,n,m,maxb; 18 int b[N]; 19 20 void dfs( int p, int td ){ 21 if( visit[p] ){ 22 flag = false; 23 return ; 24 } 25 visit[p] = true; 26 maxd = td>maxd ? td : maxd; 27 if(++b[td]>maxb) maxb = b[td]; 28 for( int i=1 ; i<=n ; i++ ){ 29 if( buffer[p][i] ){ 30 if(!flag) return ; 31 dfs(i,td+1); 32 }else 33 continue; 34 } 35 } 36 37 int main(){ 38 int x,y; 39 while( cin>>n>>m && n ){ 40 memset(buffer,0,sizeof(buffer)); 41 memset(visit,0,sizeof(visit)); 42 memset(isroot,true,sizeof(isroot)); 43 flag = true; 44 if(m>=n) flag = false; 45 for( int i=0 ; i<m ; i++ ){ 46 cin >> x >> y; 47 buffer[x][y] = true; 48 isroot[y] = false; 49 } 50 maxd = maxb = 0; 51 memset(b,0,sizeof(b)); 52 for( int i=1 ; i<=n ; i++ ) 53 if( isroot[i] ) dfs(i,0); 54 for( int i=1 ; i<=n ; i++ ){ 55 if( !visit[i] ){ 56 flag = false; 57 break; 58 } 59 } 60 if( flag ) cout << maxd << " " << maxb; 61 else cout << "INVALID"; 62 cout << endl; 63 } 64 return 0; 65 }