質問: false; //既に探索済みの場所を参照すれば閉路確定 } } } if(isTree) ans++; } cout << ans << endl; } ``` #### アルゴリズム 今回私が考えたアルゴリズムは, 1.mapに親頂点をkey,子頂点の集合をvalueとして格納. 2.for文(repマクロを使用しています)で探索開始点を決定. 3.探索済みの頂点をchecklistに記録しつつ深さ優先探索. 3-1.現在参照中の頂点をnowに格納. 3-2.子頂点の集合をスタックstに格納. 3-3.このとき,子頂点のうち一つでも探索済みの頂点を参照すれば,木構造でないと判定. 4.3をスタックの長さが0になるまで繰り返し. 5.2~4を全ての頂点を探索し終えるまで繰り返し. 6.答えを出力. といった感じです. WAの原因となりそうなものがあれば指摘を頂きたいです.
回答: 全く別の解法ですが Union Find使って 閉路を検知しつつグラフを構築してやれば あとは数えるだけです