首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。