Codeforces Round #686 (Div. 3) - E. Number of Simple Paths
解説
問題文をよーーーーーーく読むと個の頂点と
個の辺があって、連結です。
つまり、
のようにサイクルにひげが生えた形になります。
グッと睨むと、サイクルからの頂点からの最短経路がどこから来るかでグループわけできて、
- 同じグループなら行き方は1通り
- 違うグループならサイクルを右回りと左回りで2通り
あることに気づきます。
よって求めることができました。(下の実装は極小サイクル取ってくるライブラリ貼ってるのであとで書きなおしておきます)
