Aizu Competitive Programming Camp 2019 Day 1 C: 同値命題

典型って感じがした、でもその典型知識を知らなかった…

問題文概要

個の命題があり、各命題にはまでの番号が振られている。また、『ならばである』という情報が個与えられる。
『ならば』かつ『ならば』であるとき、命題と命題は同値であるとする。
各命題に対して、と同値な命題をすべて出力せよ。
https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2019Day1/problems/C

制約

• 
• 

考察

『ならば』かつ『ならば』であるとき、『ならば』が成り立つ。さらに『ならば』が成り立つなら、は互いに同値であり、この3つの命題間において『(任意の命題)ならば(任意の命題)』が成り立つことがわかる。

この、『(任意の命題)ならば(任意の命題)』が成り立つようなグループ分けをしたい！！

必要な知識

以降、各命題を頂点とみた有向グラフに置き換えて考える。上記の考察のような、『お互いに行き来できる』を満たすように頂点をグループ分けすることを強連結成分分解という。強連結成分分解は、DFS(深さ優先探索)を用いて行うことができる。
mathtrain.jp

解法

からの方向に辺を張った有向グラフと、逆方向に辺を張った有向グラフを構築する。まず、有向グラフの中の適当な頂点からDFSを行い、帰りがけ順(探索が終わった順)に番号を振っていく。すべての頂点に番号が振られるまでDFSを繰り返す。

次にに対して、先ほど振った番号が大きい順にDFSを行って、探索した頂点を一つのグループにまとめる。すべての頂点がグループに分けられるまでDFSを繰り返す。

あとは、各頂点についてグループ内の番号を昇順にソートして出力すれば良い。

のDFSとのDFSそれぞれにおいて、各頂点と各辺は高々一度しか見られないので計算量は、頂点グループのソートにかかるので、全体としてはの計算量となる。

実装

#include <bits/stdc++.h>
#define REP(i, x) for(ll i = 0; i < (x); i ++)
typedef long long ll;
using namespace std;

using graph = vector<vector<ll>>;

graph g; // 順方向に辺を張ったグラフ
graph rev_g; // 逆方向に辺を張ったグラフ
vector<bool> seen; // 頂点を見たかどうか
vector<ll> numbering; // dfs()の帰りがけ順に頂点番号を格納する
vector<ll> scc; // 頂点番号がgroupのグループに属するか返す
vector<vector<ll>> group; // グループごとに属する頂点番号を格納

void dfs(ll v){
    seen[v] = true;
    for(auto next_v : g[v]){
        if(seen[next_v]) continue;
        dfs(next_v);
    }
    numbering.push_back(v);
    return;
}

void rev_dfs(ll v, ll num){
    seen[v] = true;
    group[num].push_back(v);
    scc[v] = num;
    for(auto next_v : rev_g[v]){
        if(seen[next_v]) continue;
        rev_dfs(next_v, num);
    }
}

int main(){
    ll n, m;
    cin >> n >> m;
    g.resize(n);
    rev_g.resize(n);
    REP(i, m){
        ll a, b;
        cin >> a >> b;
        a --, b --;
        g[a].push_back(b);
        rev_g[b].push_back(a);
    }

    seen.resize(n);
    REP(i, n){
        // 全頂点を未探索に初期化
        seen[i] = false;
    }

    REP(v, n){
        if(seen[v] == false) dfs(v);
    }
    // 番号が大きい順に見たいので配列を反転させる
    reverse(numbering.begin(), numbering.end());

    REP(i, n){
        seen[i] = false;
    }

    scc.resize(n);

    ll num = 0;
    for(auto v : numbering){
        if(seen[v] == false){
            group.push_back(vector<ll>());
            rev_dfs(v, num);
            num ++;
        }
    }

    REP(i, num){
        sort(group[i].begin(), group[i].end());
    }

    REP(v, n){
        ll i = scc[v];
        for(auto ite = group[i].begin(); ite < group[i].end(); ite ++){
            cout << (*ite) + 1;
            if(ite != group[i].end() - 1) cout << " ";
        }
        cout << endl;
    }

    return 0;
}

メモ

グループ分けをするアルゴリズムといえばUnion-Findも有名で、最初Union-Findを使って無理やり実装しようとしていた…全然違うアルゴリズムなので混同に注意！！