首页 > 代码库 > sicily 1034. Forest

sicily 1034. Forest

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
 Copy sample input to clipboard 
1 01 11 13 11 32 21 22 10 88
Sample Output
0 1INVALID1 2INVALID

 

这题主要考虑环的问题吧,还有要注意的就是单个元素自身成环和没有根节点的情况
#include <iostream>#include <cstring>#include <stack>#include <vector>using namespace std;struct Node{    Node(int v = -1, int l = 0):value(v), level(l) { }    int value;    int level;};int main(int argc, char const *argv[]){    int n, m, a, b;    int level[101];  // 记录每层的个数    bool visited[101];  // 用于判断是否形成环    while (cin >> n >> m && n != 0) {        vector<int> node[101];        Node parent[101];  // 记录父节点        memset(level, 0, sizeof(level));        memset(visited, false, sizeof(visited));        bool isSucceed = true;        for (int i = 0; i != m; ++i) {            cin >> a >> b;            if (a == b) {  // 元素指向自身                isSucceed = false;                continue;            }            node[a - 1].push_back(b - 1);  // 元素值是从 1 开始的            if (parent[b - 1].value =http://www.mamicode.com/= -1)                parent[b - 1].value = http://www.mamicode.com/a - 1;            else                isSucceed = false;        }        bool hasRoot = false;  // 是否有根节点        if (isSucceed) {            for (int i = 0; i != n; ++i) {                if (!isSucceed)                    break;                if (parent[i].value =http://www.mamicode.com/= -1) {  // 从根节点遍历每一棵树                    hasRoot = true;                    stack<int> s;                    s.push(i);                    while (!s.empty()) {                        if (!isSucceed)                            break;                        int current = s.top();                        visited[current] = true;                        if (current != i)                            parent[current].level = parent[parent[current].value].level + 1;  // 子节点level等于父节点+1                        s.pop();                        for (int j = 0; j != node[current].size(); ++j) {                            if (visited[node[current][j]]) {  // 形成了环                                isSucceed = false;                                break;                            }                            s.push(node[current][j]);                        }                    }                }            }        }        if (isSucceed) {            for (int i = 0; i != n; ++i) {                level[parent[i].level]++;            }        }        if (!isSucceed || !hasRoot) {            cout << "INVALID" << endl;            continue;        }        int levelMax = -1;        int index = -1;        for (int i = 0; i != n; ++i) {            if (level[i] == 0)                break;            if (levelMax < level[i]) {                levelMax = level[i];            }            index++;        }        cout << index << " " << levelMax << endl;    }    return 0;}

 

sicily 1034. Forest