n度あることはn+1度ある

憶測が多いブログなので鵜呑みにしないこと

ABC068 C - Cat Snuke and a Voyage

Union-Findを用いた解法で解いてみました。(Union-Findは前回紹介したものを使用)
入力が(a,b) ≠ (1,N)なので単純に以下のように解けます。ただしUnion-Findが実力を発揮するのは、a番目からb番目の島にたどり着けるか?のような問題だと思います。少々贅沢な解法だと思いますが、ぱっと思い浮かんだものがこれでした。
この問題は解説にもあるように、配列を使ったものがスマートだと思いました。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i < int(n); i++)
 
struct UnionFind{
  vector<int> par;
  vector<int> sizes;
  UnionFind(int n) : par(n), sizes(n, 1) {
    rep(i,n) par[i] = i;
  }
  int find(int x) {
    if (x == par[x]) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (sizes[x] < sizes[y]) swap(x, y);
    par[y] = x;
    sizes[x] += sizes[y];
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
};
int main(){
    int n,m;
    cin>>n>>m;
    UnionFind un(n+1);
    for(int i = 0; i < m; i++){
        int a,b;
        cin>>a>>b;
        if(a==1||b==n)
            un.unite(a,b);
    }
    if(un.same(1,n))
        cout<<"POSSIBLE";
    else
        cout<<"IMPOSSIBLE";
}