SRM660 div2 500

問題

N人の友達をパーティーに招待する。
しかし、友だちiは友だちA[i]が嫌いなので、もし先にパーティーに招待されていたら来ない。
(嫌いな人がいない場合はA[i]=iとなっている)
呼べる友達が最大になるような順番で友達を招待したら、何人の友達を呼ぶことができるか？

N<=50

考え方

順番の考慮が必要な友達集合に分解する。
これは、UnionFindなんかで、まとめあげればよい。

もし、順番の考慮が必要な友達集合を考えてみると、嫌いな友達よりも先に呼ばれるようにするために友だちiから友だちA[i]に矢印を伸ばすような有向グラフで考えることができる。
各ノードからは1本しか辺がでないので、A[i]=iを2つ含むような場合はあり得なくて、A[i]=iを一つ含むような場合は、そこを最後にすれば全員を呼ぶことができ、A[i]=iを含まないような場合は、サイクルが1つできているはずなので、そのサイクルから1人抜いた他の全員呼べる。

なので、A[i]=iがあればn、A[i]=iが無ければn-1をそれぞれ友達集合について足し合わせたものが答えになる。