首页 > 代码库 > Sicily 1034. Forest

Sicily 1034. Forest

题目地址:1034. Forest

思路:

     待续.......

     具体代码如下:

 1 #include <iostream> 2 #include <cstring> 3 #include <queue> 4 using namespace std; 5  6 bool path[101][101]; 7 bool visited[101]; 8 bool Root[101]; 9 10 int main()11 {12     int n, m;13     while (cin >> n >> m && n)14     {15         memset(path, false, sizeof(path));16         memset(visited, false, sizeof(visited));17         memset(Root, true, sizeof(Root));18 19         bool flag = n > m ? true : false;20         for (int i = 1; i <= m; i++)21         {22             int node1, node2;23             cin >> node1 >> node2;24             if (node1 == node2) flag = false;25             path[node1][node2] = true;26         }27         if (flag == false) {28             cout << "INVALID\n";29             continue;30         }31         32         for (int i = 1; i <= n; i++)33             for (int j = 1; j <= n; j++)34                 if (path[j][i])35                     Root[i] = false;36         int maxwidth = 0;37         for (int i = 1; i <= n; i++)38             if (Root[i]) {39                 maxwidth++;40                 visited[i] = true;41             }42         queue<int> store;43         int depth, maxdepth;44         maxdepth = depth = 0;45         int width[101] = {0};46         for (int i = 1; i <= n; i++)47         {48             if (Root[i])49             {50                 store.push(i);51                 depth = 0;52                 while (!store.empty())53                 {54                     int size = store.size();55                     width[depth] += size;56                     while (size--)57                     {58                         for (int j = 1; j <= n; j++)59                             if (path[store.front()][j])60                             {61                                 if (!visited[j]) {62                                     store.push(j);63                                     visited[j] = true;64                                 }65                                 else66                                     flag = false;67                             }68                         store.pop();69                     }70                     if (!store.empty())71                         depth++;72                 }73                 maxdepth = depth > maxdepth ? depth : maxdepth;74             }75         }76         77         for (int i = 1; i <= n; i++)78             if (!visited[i]) {79                 flag = false;80                 break;81             }82         83         for (int i = 0; i <= maxdepth; i++)84             maxwidth = width[i] > maxwidth ? width[i] : maxwidth;85         86         flag == false ? cout << "INVALID" : cout << maxdepth << " " << maxwidth;87         cout << endl;88     }89 90     return 0;91 }

 

Sicily 1034. Forest