Cat Snuke and a Voyage [AtCoder Regular Contest 079 C]

http://arc079.contest.atcoder.jp/tasks/arc079_a

解法

http://arc079.contest.atcoder.jp/submissions/1462430

「島1 -> 島x -> 島N」という経路があるかという問題。
xは[2,N-1]であり、これを全探索することにする。
あとは、島1と島xの間、島xと島Nの間にそれぞれ辺があるかを見れば良い。
これは、辺をset>で保持しておいて、それを確認していくのがよい。
「島1 -> 島x -> 島N」という経路があれば、"POSSIBLE"

int N, M;
set<pair<int, int>> E;
//---------------------------------------------------------------------------------------------------
string solve() {
    rep(i, 1, N - 1) {
        if (E.count({ 0,i }) && E.count({ i, N - 1 })) return "POSSIBLE";
    }
    return "IMPOSSIBLE";
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        int a, b; cin >> a >> b;
        a--; b--;
        E.insert({ a,b });
        E.insert({ b,a });
    }
 
    cout << solve() << endl;
}