<title>1094 The Largest Generation (25分) | Hexo</title>

<metaname="viewport"content="width=device-width, initial-scale=1, maximum-scale=1">

<metaname="description"content="树的遍历题意：给出谱系图（多叉树)，求最多孩子的那一层的深度和宽度。 DFS遍历，记录每层的宽度，找最大的那个即可也可以用BFS做 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include &lt;bits&#x2F;stdc++.h&gt;using namespace">

<metaname="description"content="树的遍历题意：给出谱系图（多叉树)，求最多孩子的那一层的深度和宽度。 DFS遍历，记录每层的宽度，找最大的那个即可也可以用BFS做 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include &lt;bits&#x2F;stdc++.h&gt;using namespace std;c">

<metaproperty="og:type"content="article">

<metaproperty="og:title"content="1094 The Largest Generation (25分)">

<metaproperty="og:url"content="http://yoursite.com/2020/03/02/1094%20The%20Largest%20Generation%20(25%E5%88%86)/index.html">

<metaproperty="og:site_name"content="Hexo">

<metaproperty="og:description"content="树的遍历题意：给出谱系图（多叉树)，求最多孩子的那一层的深度和宽度。 DFS遍历，记录每层的宽度，找最大的那个即可也可以用BFS做 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include &lt;bits&#x2F;stdc++.h&gt;using namespace">

<metaproperty="og:description"content="树的遍历题意：给出谱系图（多叉树)，求最多孩子的那一层的深度和宽度。 DFS遍历，记录每层的宽度，找最大的那个即可也可以用BFS做 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include &lt;bits&#x2F;stdc++.h&gt;using namespace std;c">

<metaproperty="og:locale"content="en_US">

<metaproperty="article:published_time"content="2020-03-02T03:50:29.787Z">

<metaproperty="article:modified_time"content="2020-03-02T03:50:29.787Z">

<metaproperty="article:modified_time"content="2020-03-05T03:44:07.840Z">

<metaproperty="article:author"content="John Doe">

<metaname="twitter:card"content="summary">

<p>树的遍历<br><br>题意：给出谱系图（多叉树)，求最多孩子的那一层的深度和宽度。</p>

<p>DFS遍历，记录每层的宽度，找最大的那个即可<br><br>也可以用BFS做</p>

<figureclass="highlight plain"><table><tr><tdclass="gutter"><pre><spanclass="line">1</span><br><spanclass="line">2</span><br><spanclass="line">3</span><br><spanclass="line">4</span><br><spanclass="line">5</span><br><spanclass="line">6</span><br><spanclass="line">7</span><br><spanclass="line">8</span><br><spanclass="line">9</span><br><spanclass="line">10</span><br><spanclass="line">11</span><br><spanclass="line">12</span><br><spanclass="line">13</span><br><spanclass="line">14</span><br><spanclass="line">15</span><br><spanclass="line">16</span><br><spanclass="line">17</span><br><spanclass="line">18</span><br><spanclass="line">19</span><br><spanclass="line">20</span><br><spanclass="line">21</span><br><spanclass="line">22</span><br><spanclass="line">23</span><br><spanclass="line">24</span><br><spanclass="line">25</span><br><spanclass="line">26</span><br><spanclass="line">27</span><br><spanclass="line">28</span><br><spanclass="line">29</span><br><spanclass="line">30</span><br><spanclass="line">31</span><br><spanclass="line">32</span><br><spanclass="line">33</span><br><spanclass="line">34</span><br><spanclass="line">35</span><br><spanclass="line">36</span><br><spanclass="line">37</span><br><spanclass="line">38</span><br><spanclass="line">39</span><br><spanclass="line">40</span><br><spanclass="line">41</span><br><spanclass="line">42</span><br><spanclass="line">43</span><br><spanclass="line">44</span><br><spanclass="line">45</span><br><spanclass="line">46</span><br></pre></td><tdclass="code"><pre><spanclass="line">#include &lt;bits&#x2F;stdc++.h&gt;</span><br><spanclass="line">using namespace std;</span><br><spanclass="line">const int maxn &#x3D; 100 + 10;</span><br><spanclass="line"></span><br><spanclass="line">vector&lt;int&gt; tree[maxn];</span><br><spanclass="line">int level[maxn];</span><br><spanclass="line">bool vis[maxn];</span><br><spanclass="line"></span><br><spanclass="line">void DFS(int root, int cnt) &#123;</span><br><spanclass="line">level[cnt]++;</span><br><spanclass="line">for (int i &#x3D; 0; i &lt; tree[root].size(); ++i)</span><br><spanclass="line">DFS(tree[root][i], cnt + 1);</span><br><spanclass="line">&#125;</span><br><spanclass="line"></span><br><spanclass="line">int main(int argc, char const *argv[])</span><br><spanclass="line">&#123;</span><br><spanclass="line">int N, M, j &#x3D; 1, cnt &#x3D; 0, ans, root;</span><br><spanclass="line">cin &gt;&gt; N &gt;&gt; M;</span><br><spanclass="line">memset(vis, false, sizeof(vis));</span><br><spanclass="line">for (int i &#x3D; 0; i &lt; M; ++i) &#123;</span><br><spanclass="line">int ID, K, t;</span><br><spanclass="line">cin &gt;&gt; ID &gt;&gt; K;</span><br><spanclass="line">for (int j &#x3D; 0; j &lt; K; ++j) &#123;</span><br><spanclass="line">cin &gt;&gt; t;</span><br><spanclass="line">tree[ID].push_back(t);</span><br><spanclass="line">vis[t] &#x3D; true;</span><br><spanclass="line">&#125;</span><br><spanclass="line">&#125;</span><br><spanclass="line">for (int i &#x3D; 1; i &lt;&#x3D; N; ++i) &#123;</span><br><spanclass="line">if (!vis[i]) &#123;</span><br><spanclass="line">root &#x3D; i;</span><br><spanclass="line">break;</span><br><spanclass="line">&#125;</span><br><spanclass="line">&#125;</span><br><spanclass="line">DFS(root, 1);</span><br><spanclass="line">while (level[j] !&#x3D; 0) &#123;</span><br><spanclass="line">if (level[j] &gt; cnt) &#123;</span><br><spanclass="line">ans &#x3D; j;</span><br><spanclass="line">cnt &#x3D; level[j];</span><br><spanclass="line">&#125;</span><br><spanclass="line">j++;</span><br><spanclass="line">&#125;</span><br><spanclass="line">cout &lt;&lt; cnt &lt;&lt; &quot; &quot; &lt;&lt; ans &lt;&lt; endl;</span><br><spanclass="line"></span><br><spanclass="line">return 0;</span><br><spanclass="line">&#125;</span><br></pre></td></tr></table></figure>

<figureclass="highlight c++"><table><tr><tdclass="gutter"><pre><spanclass="line">1</span><br><spanclass="line">2</span><br><spanclass="line">3</span><br><spanclass="line">4</span><br><spanclass="line">5</span><br><spanclass="line">6</span><br><spanclass="line">7</span><br><spanclass="line">8</span><br><spanclass="line">9</span><br><spanclass="line">10</span><br><spanclass="line">11</span><br><spanclass="line">12</span><br><spanclass="line">13</span><br><spanclass="line">14</span><br><spanclass="line">15</span><br><spanclass="line">16</span><br><spanclass="line">17</span><br><spanclass="line">18</span><br><spanclass="line">19</span><br><spanclass="line">20</span><br><spanclass="line">21</span><br><spanclass="line">22</span><br><spanclass="line">23</span><br><spanclass="line">24</span><br><spanclass="line">25</span><br><spanclass="line">26</span><br><spanclass="line">27</span><br><spanclass="line">28</span><br><spanclass="line">29</span><br><spanclass="line">30</span><br><spanclass="line">31</span><br><spanclass="line">32</span><br><spanclass="line">33</span><br><spanclass="line">34</span><br><spanclass="line">35</span><br><spanclass="line">36</span><br><spanclass="line">37</span><br><spanclass="line">38</span><br><spanclass="line">39</span><br><spanclass="line">40</span><br><spanclass="line">41</span><br><spanclass="line">42</span><br><spanclass="line">43</span><br><spanclass="line">44</span><br><spanclass="line">45</span><br><spanclass="line">46</span><br></pre></td><tdclass="code"><pre><spanclass="line"><spanclass="meta">#<spanclass="meta-keyword">include</span><spanclass="meta-string">&lt;bits/stdc++.h&gt;</span></span></span><br><spanclass="line"><spanclass="keyword">using</span><spanclass="keyword">namespace</span><spanclass="built_in">std</span>;</span><br><spanclass="line"><spanclass="keyword">const</span><spanclass="keyword">int</span> maxn =<spanclass="number">100</span> +<spanclass="number">10</span>;</span><br><spanclass="line"></span><br><spanclass="line"><spanclass="built_in">vector</span>&lt;<spanclass="keyword">int</span>&gt; tree[maxn];</span><br><spanclass="line"><spanclass="keyword">int</span> level[maxn];</span><br><spanclass="line"><spanclass="keyword">bool</span> vis[maxn];</span><br><spanclass="line"></span><br><spanclass="line"><spanclass="function"><spanclass="keyword">void</span><spanclass="title">DFS</span><spanclass="params">(<spanclass="keyword">int</span> root,<spanclass="keyword">int</span> cnt)</span></span>&#123;</span><br><spanclass="line">level[cnt]++;</span><br><spanclass="line"><spanclass="keyword">for</span> (<spanclass="keyword">int</span> i =<spanclass="number">0</span>; i &lt; tree[root].<spanclass="built_in">size</span>(); ++i)</span><br><spanclass="line">DFS(tree[root][i], cnt +<spanclass="number">1</span>);</span><br><spanclass="line">&#125;</span><br><spanclass="line"></span><br><spanclass="line"><spanclass="function"><spanclass="keyword">int</span><spanclass="title">main</span><spanclass="params">(<spanclass="keyword">int</span> argc,<spanclass="keyword">char</span><spanclass="keyword">const</span> *argv[])</span></span></span><br><spanclass="line"><spanclass="function"></span>&#123;</span><br><spanclass="line"><spanclass="keyword">int</span> N, M, j =<spanclass="number">1</span>, cnt =<spanclass="number">0</span>, ans, root;</span><br><spanclass="line"><spanclass="built_in">cin</span> &gt;&gt; N &gt;&gt; M;</span><br><spanclass="line"><spanclass="built_in">memset</span>(vis,<spanclass="literal">false</span>,<spanclass="keyword">sizeof</span>(vis));</span><br><spanclass="line"><spanclass="keyword">for</span> (<spanclass="keyword">int</span> i =<spanclass="number">0</span>; i &lt; M; ++i) &#123;</span><br><spanclass="line"><spanclass="keyword">int</span> ID, K, t;</span><br><spanclass="line"><spanclass="built_in">cin</span> &gt;&gt; ID &gt;&gt; K;</span><br><spanclass="line"><spanclass="keyword">for</span> (<spanclass="keyword">int</span> j =<spanclass="number">0</span>; j &lt; K; ++j) &#123;</span><br><spanclass="line"><spanclass="built_in">cin</span> &gt;&gt; t;</span><br><spanclass="line">tree[ID].push_back(t);</span><br><spanclass="line">vis[t] =<spanclass="literal">true</span>;</span><br><spanclass="line">&#125;</span><br><spanclass="line">&#125;</span><br><spanclass="line"><spanclass="keyword">for</span> (<spanclass="keyword">int</span> i =<spanclass="number">1</span>; i &lt;= N; ++i) &#123;</span><br><spanclass="line"><spanclass="keyword">if</span> (!vis[i]) &#123;</span><br><spanclass="line">root = i;</span><br><spanclass="line"><spanclass="keyword">break</span>;</span><br><spanclass="line">&#125;</span><br><spanclass="line">&#125;</span><br><spanclass="line">DFS(root,<spanclass="number">1</span>);</span><br><spanclass="line"><spanclass="keyword">while</span> (level[j] !=<spanclass="number">0</span>) &#123;</span><br><spanclass="line"><spanclass="keyword">if</span> (level[j] &gt; cnt) &#123;</span><br><spanclass="line">ans = j;</span><br><spanclass="line">cnt = level[j];</span><br><spanclass="line">&#125;</span><br><spanclass="line">j++;</span><br><spanclass="line">&#125;</span><br><spanclass="line"><spanclass="built_in">cout</span> &lt;&lt; cnt &lt;&lt;<spanclass="string">" "</span> &lt;&lt; ans &lt;&lt;<spanclass="built_in">endl</span>;</span><br><spanclass="line"></span><br><spanclass="line"><spanclass="keyword">return</span><spanclass="number">0</span>;</span><br><spanclass="line">&#125;</span><br></pre></td></tr></table></figure>

<metaproperty="og:locale"content="en_US">

<metaproperty="og:image"content="https://i.loli.net/2020/03/04/X2rieZHWd7UNMEK.png">

<metaproperty="article:published_time"content="2020-03-04T01:31:02.291Z">

<metaproperty="article:modified_time"content="2020-03-04T01:31:02.373Z">

<metaproperty="article:modified_time"content="2020-03-05T03:44:01.815Z">

<metaproperty="article:author"content="John Doe">

<metaname="twitter:card"content="summary">

<metaname="twitter:image"content="https://i.loli.net/2020/03/04/X2rieZHWd7UNMEK.png">

<p>利用完全二叉树建立结构，中序遍历填入元素</p>

<p><imgsrc="https://i.loli.net/2020/03/04/X2rieZHWd7UNMEK.png"alt="clipboard.png"></p>

<figureclass="highlight plain"><table><tr><tdclass="gutter"><pre><spanclass="line">1</span><br><spanclass="line">2</span><br><spanclass="line">3</span><br><spanclass="line">4</span><br><spanclass="line">5</span><br><spanclass="line">6</span><br><spanclass="line">7</span><br><spanclass="line">8</span><br><spanclass="line">9</span><br><spanclass="line">10</span><br><spanclass="line">11</span><br><spanclass="line">12</span><br><spanclass="line">13</span><br><spanclass="line">14</span><br><spanclass="line">15</span><br><spanclass="line">16</span><br><spanclass="line">17</span><br><spanclass="line">18</span><br><spanclass="line">19</span><br><spanclass="line">20</span><br><spanclass="line">21</span><br><spanclass="line">22</span><br><spanclass="line">23</span><br><spanclass="line">24</span><br><spanclass="line">25</span><br><spanclass="line">26</span><br><spanclass="line">27</span><br></pre></td><tdclass="code"><pre><spanclass="line">#include &lt;bits&#x2F;stdc++.h&gt;</span><br><spanclass="line">using namespace std;</span><br><spanclass="line">const int maxn &#x3D; 1000 + 10;</span><br><spanclass="line"></span><br><spanclass="line">int a[maxn], ans[maxn], cnt, N, i;</span><br><spanclass="line">void in_order(int root) &#123;</span><br><spanclass="line">if (root &gt; N)</span><br><spanclass="line">return;</span><br><spanclass="line">in_order(root * 2);</span><br><spanclass="line">ans[root] &#x3D; a[cnt++];</span><br><spanclass="line">in_order(root * 2 + 1);</span><br><spanclass="line">&#125;</span><br><spanclass="line"></span><br><spanclass="line">int main(int argc, char const *argv[])</span><br><spanclass="line">&#123;</span><br><spanclass="line">cin &gt;&gt; N;</span><br><spanclass="line">for (i &#x3D; 0; i &lt; N; ++i)</span><br><spanclass="line">cin &gt;&gt; a[i];</span><br><spanclass="line">sort(a, a + N);</span><br><spanclass="line">cnt &#x3D; 0;</span><br><spanclass="line">in_order(1);</span><br><spanclass="line">for (i &#x3D; 1; i &lt;&#x3D; N - 1; ++i)</span><br><spanclass="line">cout &lt;&lt; ans[i] &lt;&lt; &quot; &quot;;</span><br><spanclass="line">cout &lt;&lt; ans[i] &lt;&lt; endl;</span><br><spanclass="line"></span><br><spanclass="line">return 0;</span><br><spanclass="line">&#125;</span><br></pre></td></tr></table></figure>

<figureclass="highlight c++"><table><tr><tdclass="gutter"><pre><spanclass="line">1</span><br><spanclass="line">2</span><br><spanclass="line">3</span><br><spanclass="line">4</span><br><spanclass="line">5</span><br><spanclass="line">6</span><br><spanclass="line">7</span><br><spanclass="line">8</span><br><spanclass="line">9</span><br><spanclass="line">10</span><br><spanclass="line">11</span><br><spanclass="line">12</span><br><spanclass="line">13</span><br><spanclass="line">14</span><br><spanclass="line">15</span><br><spanclass="line">16</span><br><spanclass="line">17</span><br><spanclass="line">18</span><br><spanclass="line">19</span><br><spanclass="line">20</span><br><spanclass="line">21</span><br><spanclass="line">22</span><br><spanclass="line">23</span><br><spanclass="line">24</span><br><spanclass="line">25</span><br><spanclass="line">26</span><br><spanclass="line">27</span><br></pre></td><tdclass="code"><pre><spanclass="line"><spanclass="meta">#<spanclass="meta-keyword">include</span><spanclass="meta-string">&lt;bits/stdc++.h&gt;</span></span></span><br><spanclass="line"><spanclass="keyword">using</span><spanclass="keyword">namespace</span><spanclass="built_in">std</span>;</span><br><spanclass="line"><spanclass="keyword">const</span><spanclass="keyword">int</span> maxn =<spanclass="number">1000</span> +<spanclass="number">10</span>;</span><br><spanclass="line"></span><br><spanclass="line"><spanclass="keyword">int</span> a[maxn], ans[maxn], cnt, N, i;</span><br><spanclass="line"><spanclass="function"><spanclass="keyword">void</span><spanclass="title">in_order</span><spanclass="params">(<spanclass="keyword">int</span> root)</span></span>&#123;</span><br><spanclass="line"><spanclass="keyword">if</span> (root &gt; N)</span><br><spanclass="line"><spanclass="keyword">return</span>;</span><br><spanclass="line">in_order(root *<spanclass="number">2</span>);</span><br><spanclass="line">ans[root] = a[cnt++];</span><br><spanclass="line">in_order(root *<spanclass="number">2</span> +<spanclass="number">1</span>);</span><br><spanclass="line">&#125;</span><br><spanclass="line"></span><br><spanclass="line"><spanclass="function"><spanclass="keyword">int</span><spanclass="title">main</span><spanclass="params">(<spanclass="keyword">int</span> argc,<spanclass="keyword">char</span><spanclass="keyword">const</span> *argv[])</span></span></span><br><spanclass="line"><spanclass="function"></span>&#123;</span><br><spanclass="line"><spanclass="built_in">cin</span> &gt;&gt; N;</span><br><spanclass="line"><spanclass="keyword">for</span> (i =<spanclass="number">0</span>; i &lt; N; ++i)</span><br><spanclass="line"><spanclass="built_in">cin</span> &gt;&gt; a[i];</span><br><spanclass="line">sort(a, a + N);</span><br><spanclass="line">cnt =<spanclass="number">0</span>;</span><br><spanclass="line">in_order(<spanclass="number">1</span>);</span><br><spanclass="line"><spanclass="keyword">for</span> (i =<spanclass="number">1</span>; i &lt;= N -<spanclass="number">1</span>; ++i)</span><br><spanclass="line"><spanclass="built_in">cout</span> &lt;&lt; ans[i] &lt;&lt;<spanclass="string">" "</span>;</span><br><spanclass="line"><spanclass="built_in">cout</span> &lt;&lt; ans[i] &lt;&lt;<spanclass="built_in">endl</span>;</span><br><spanclass="line"></span><br><spanclass="line"><spanclass="keyword">return</span><spanclass="number">0</span>;</span><br><spanclass="line">&#125;</span><br></pre></td></tr></table></figure>