Sicily 1034. Forest

题目地址：1034. Forest

思路：

网上很多说用深搜，很任性…….发现广搜也挺好用的，实验课打的(⊙o⊙)…orz……..囧。

先找根结点，根据根结点广搜深度，广搜宽度，不过要开一个数组，同一层的累加宽度。别忘了要判断是否合法。

具体代码如下：

 #include <iostream>
 #include <cstring>
 #include <queue>
 using namespace std; bool path[][];
 bool visited[];
 bool Root[]; int main()
 {
     int n, m;
     while (cin >> n >> m && n)
     {
         memset(path, false, sizeof(path));
         memset(visited, false, sizeof(visited));
         memset(Root, true, sizeof(Root));         bool flag = n > m ? true : false;
         for (int i = ; i <= m; i++)
         {
             int node1, node2;
             cin >> node1 >> node2;
             if (node1 == node2) flag = false;
             path[node1][node2] = true;
         }
         if (flag == false) {
             cout << "INVALID\n";
             continue;
         }         for (int i = ; i <= n; i++)
             for (int j = ; j <= n; j++)
                 if (path[j][i])
                     Root[i] = false;
         int maxwidth = ;
         for (int i = ; i <= n; i++)
             if (Root[i]) {
                 maxwidth++;
                 visited[i] = true;
             }
         queue<int> store;
         int depth, maxdepth;
         maxdepth = depth = ;
         int width[] = {};
         for (int i = ; i <= n; i++)
         {
             if (Root[i])
             {
                 store.push(i);
                 depth = ;
                 while (!store.empty())
                 {
                     int size = store.size();
                     width[depth] += size;
                     while (size--)
                     {
                         for (int j = ; j <= n; j++)
                             if (path[store.front()][j])
                             {
                                 if (!visited[j]) {
                                     store.push(j);
                                     visited[j] = true;
                                 }
                                 else
                                     flag = false;
                             }
                         store.pop();
                     }
                     if (!store.empty())
                         depth++;
                 }
                 maxdepth = depth > maxdepth ? depth : maxdepth;
             }
         }         for (int i = ; i <= n; i++)
             if (!visited[i]) {
                 flag = false;
                 break;
             }         for (int i = ; i <= maxdepth; i++)
             maxwidth = width[i] > maxwidth ? width[i] : maxwidth;         flag == false ? cout << "INVALID" : cout << maxdepth << " " << maxwidth;
         cout << endl;
     }     return ;
 }