- 思路：
- 网上很多说用深搜，很任性…….发现广搜也挺好用的，实验课打的(⊙o⊙)…orz……..囧。
- 先找根结点，根据根结点广搜深度，广搜宽度，不过要开一个数组，同一层的累加宽度。别忘了要判断是否合法。
- 具体代码如下：
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
bool path[101][101];
bool visited[101];
bool Root[101];
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 = 1; 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 = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (path[j][i])
Root[i] = false;
int maxwidth = 0;
for (int i = 1; i <= n; i++)
if (Root[i]) {
maxwidth++;
visited[i] = true;
}
queue<int> store;
int depth, maxdepth;
maxdepth = depth = 0;
int width[101] = {0};
for (int i = 1; i <= n; i++)
{
if (Root[i])
{
store.push(i);
depth = 0;
while (!store.empty())
{
int size = store.size();
width[depth] += size;
while (size--)
{
for (int j = 1; 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 = 1; i <= n; i++)
if (!visited[i]) {
flag = false;
break;
}
for (int i = 0; i <= maxdepth; i++)
maxwidth = width[i] > maxwidth ? width[i] : maxwidth;
flag == false ? cout << "INVALID" : cout << maxdepth << " " << maxwidth;
cout << endl;
}
return 0;
}