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; }