mmxsrup https://blog.hatena.ne.jp/mmxsrup/ srupのメモ帳 https://mmxsrup.hatenablog.com/ abc dfs ワーシャルフロイド法 問題 問題概要 省略 解法 dfsで友達の友達を求めることにした。この時に、dfsの引き数として、現在の頂点と、前回の頂点、探索回数、スタート時点の頂点を持つことにした。前回の頂点は元の頂点に戻るのを禁止しするため。スタート時点を保持しておくのは、例えば、3つの頂点がループになっているときに、頂点1から始めた時に、2回の探索で、頂点3が友達の友達でないかと求まるが、実際は、1と3は友達なので、友達の友達にはならない。そこで、f[u][v]でuとvが友達であるかの情報を入れておいて、2回の探索後に友達でないことを確認すればいい。また、友達の友達を重複してカウントしないように、一度頂点番号をset… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmmxsrup.hatenablog.com%2Fentry%2F2016%2F09%2F19%2F011337" title="ABC 016 C - 友達の友達 - srupのメモ帳" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2016-09-19 01:13:37 rich https://mmxsrup.hatenablog.com/entry/2016/09/19/011337 1.0 100%