ARC079: C - Cat Snuke and a Voyage

問題

C: Cat Snuke and a Voyage - AtCoder Regular Contest 079 | AtCoder

解答

辺とについて、任意のに対しての辺の存在判定を程度で判定できるようにしておく。 〜に行くために跨ぐ点を決め打ちして、全体で以内で解を求められる。

int main() {
  int N, M; cin >> N >> M;
  set<pair<int, int>> st;
  rep (i, M) {
    int a, b; cin >> a >> b;
    st.emplace(a, b);
  }

  REP (i, 2, N) {
    if (st.count({1, i}) && st.count({i, N})) {
      std::cout << "POSSIBLE\n";
      return 0;
    }
  }

  std::cout << "IMPOSSIBLE\n";
}