はまやんはまやんはまやん

hamayanhamayan's blog

Path [「みんなのプロコン 2019」 B]

https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_b

解説

https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4206062

通るパターンを全探索しよう。
4つの街で訪れる可能性のあるパターンは4!通りなので、これをc++ならnext_permutationとかで全探索する。
辺の管理は隣接行列を使うといい。

int E[4][4];
//---------------------------------------------------------------------------------------------------
void _main() {
    rep(i, 0, 3) {
        int a, b; cin >> a >> b;
        a--; b--;
        E[a][b] = E[b][a] = 1;
    }
 
    vector<int> ord;
    rep(i, 0, 4) ord.push_back(i);
    do {
        int ng = 0;
        rep(j, 0, 3) if (!E[ord[j]][ord[j + 1]]) ng = 1;
        if(!ng) {
            printf("YES\n");
            return;
        }
    } while(next_permutation(all(ord)));
 
    printf("NO\n");
}