网站建设项目立项登记 表,沧州网站建设 网络服务,邯郸网站网站建设,建设银行网站logo题目地址#xff1a;1034. Forest 思路#xff1a; 网上很多说用深搜#xff0c;很任性.......发现广搜也挺好用的#xff0c;实验课打的(⊙o⊙)…orz........囧。 先找根结点#xff0c;根据根结点广搜深度#xff0c;广搜宽度#xff0c;不过要开一个数组#xff0c;…题目地址1034. Forest 思路 网上很多说用深搜很任性.......发现广搜也挺好用的实验课打的(⊙o⊙)…orz........囧。 先找根结点根据根结点广搜深度广搜宽度不过要开一个数组同一层的累加宽度。别忘了要判断是否合法。 具体代码如下 1 #include iostream2 #include cstring3 #include queue4 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 queueint 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 else
66 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 } 转载于:https://www.cnblogs.com/winray/p/4157235.html
