首页 > 代码库 > Sicily 1034. Forest
Sicily 1034. Forest
Constraints
Time Limit: 1 secs, Memory Limit: 32 MB
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 01 11 13 11 32 21 22 10 88
Sample Output
0 1INVALID1 2INVALID
分析：一看到题目中说到了有环的情况，立马就想到了学数据结构的时候用广搜来进行拓扑排序可以找出环。这道题同样也是用广搜，通过边遍历每一个可以放入森林的节点，每次遍历到一个节点，就删掉指向它的边，要是存在某些边没有被删除，就说明有些节点是非法的。每个节点都有一个level来表示它所在的层数，子节点的层数等于父节点层数加1。
1 #include <iostream> 2 #include <memory.h> 3 #include <queue> 4 #include <vector> 5 using namespace std; 6 7 struct Node{ 8 int id; //树中每个节点的编号 9 int level; //树中每个节点所在的层数 10 }; 11 12 struct Edge{13 int from;14 int to;15 };16 17 int main(){18 int n, m, i;19 Edge edge;20 Node node;21 Node nodes[100];22 vector<Edge>::iterator iter;23 bool isRoot[100];24 while(cin >> n >> m && n != 0){25 vector<Edge> v;26 queue<Node> q;27 memset(isRoot, true, sizeof(isRoot));28 for(i = 0; i < n; i++){29 nodes[i].id = i + 1;30 nodes[i].level = -1;31 }32 for(i = 0; i < m; i++){33 cin >> edge.from >> edge.to;34 v.push_back(edge);35 isRoot[edge.to - 1] = false; 36 }37 for(i = 0; i < n; i++){38 if(isRoot[i]){39 node.id = i + 1;40 node.level = 0;41 q.push(node);42 }43 }44 /*广搜来标记每个节点的层数*/ 45 while(!q.empty()){46 node = q.front();47 q.pop();48 for(iter = v.begin(); iter != v.end(); iter++){49 if(iter->from == node.id && nodes[iter->to -1].level == -1){50 nodes[iter->to -1].level = node.level+1;51 q.push(nodes[iter->to -1]);52 v.erase(iter); //每次找到一个合法的点就删掉一条边 53 iter--;54 }55 }56 }57 if(!v.empty()){ //有环或者存在几个父节点同时指向一个子节点 58 cout << "INVALID" << endl;59 } else {60 int sum[100]; //标记每层节点的个数 61 int max = 0;62 memset(sum, 0, sizeof(sum));63 for(i = 0; i < n; i++){64 if(nodes[i].level == -1){65 nodes[i].level = 0;66 }67 sum[nodes[i].level]++;68 }69 for(i = 0; i < 100; i++){70 if(sum[i]==0){71 break;72 }73 if(max < sum[i]){74 max = sum[i];75 }76 }77 cout << i - 1 << " " << max << endl;78 }79 }80 return 0;81 }
附加测试样例：
输入：4 2
1 2
3 4
输出：1 2
Sicily 1034. Forest