Codeforces AIM Tech Round Div.2 C Graph and String
本番はSCCに固執しすぎて実装が間に合わず．その後冷静に考えたらもっと単純な方法があった．
解法
まず気づきそうなこと：実線は辺，点線はそうでないとする．次のようなグラフの場合，bは一意に決定する．
そこで点線を辺とする(完全グラフから与えられるグラフを引いた)グラフに着目する．このグラフが下のように2つ(以上)に独立していると仮定する．
点線の両端は(a,c)で一意に決定する．
上と下のa,c同士は必ず結ばれる．
よってそのようなグラフの仮定は間違っていて，点線で構成されるグラフは連結である．それを確認した上で，(a,c)は辺で結ばれ，(a,a),(c,c)は結ばれないような判定をすればよい．幅優先探索などで深さの順番にa,c,a,c,...とメモして行って，最後に全ての頂点の組み合わせで前述の判定をすると上手くいく．
二部グラフの判定方があればそれを使えばよさそうですが，自分はあるかどうかすら知らないです．もっといい方法があれば教えて下さい)． 時間内に解けたら美味しかっただけに悔しい回でした．
