なもりグラフとは、木に１本の辺が追加された状態の無向グラフで、N本のノードに対して、N本の辺がある無向グラフ(自己ループ、多重辺はない)のことです。このグラフは１つの閉路を持ち、その閉路上の点を節とする複数の部分木から構成されています。
このグラフから各点が閉路上の点か、あるいは、どの閉路上の点を節とする部分木上の点かを求めます。
結果は、Namori.group[i]に各点iについて、-1のとき閉路上の点、それ以外の時その点が所属する閉路上の点を示します。次のようになります。
* 0 -- 1 -- 2
* | |
* 3 -- 4 -- 5 -- 6
* |
* 7
* この時、1,2,3,4は閉路をなすので group -1
* 0は閉路のノード1に所属するとして group 1
* 5,6,7は閉路のノード4に所属するとして group 4
*
実装方針
2つのDFSのステップに分けて考えます。
- STEP1: 次数が1のノードから辺を消していく。これらの点は閉路上の点ではない。この処理の結果残っているのが閉路上の点である。
- STEP2: 各閉路上の点から閉路ではない点への各辺を辿る。これらのgroupは開始した閉路上の点のindexである。
計算量は$O(N)$です。
実装(C++)
#include <bits/stdc++.h>
//#include <chrono>
using namespace std;
using ll = long long int;
#define FASTIOpre() cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20);
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
/*
* なもりグラフ
* N頂点 N辺の無向グラフは１つの閉路を含むグラフである。これを閉路とそれ以外に分解する。
* なもりグラフは閉路に木が繋がっていると見做せるので、solveした結果は、groupに
* -1のとき: 閉路
* それ以外の時: 各線のグループが所属する閉路のノード番号 を格納する。
* 例えば、次のグラフを考える。
* 0 -- 1 -- 2
* | |
* 3 -- 4 -- 5 -- 6
* |
* 7
* この時、1,2,3,4は閉路をなすので group -1
* 0は閉路のノード1に所属するとして group 1
* 5,6,7は閉路のノード4に所属するとして group 4
* を返す。
*
* Namori(n): n個の頂点のグラフを作る
* makeEdge2Way: 辺をu<->vで辺を張る
*/
struct Namori{
int n;
int alledgenum;
bool solved;
vector<vector<int>> g;
vector<int> edgecnt;
vector<int> group;
Namori(int n) : n(n) {
g = vector<vector<int>>(n, vector<int>());
edgecnt = vector<int>(n);
group = vector<int>(n, -1);
alledgenum = 0;
solved = false;
}
void makeEdge2Way(const int &u, const int &v){
// u <-> v でedgeを張る
assert(u != v);
g.at(u).push_back(v);
g.at(v).push_back(u);
++alledgenum;
++edgecnt.at(u); ++edgecnt.at(v);
}
void solve(){
assert(solved == false); // 多重solve防止
assert(alledgenum == n); // なもりグラフか？
solved = true;
vector<int> q;
vector<bool> visited(n);
// 最初に閉路を検出するDFS. 辺の数が1のノードを狩っていく。トポロジカルソートの要領で枝を刈る。
// 閉路ではない区間は一旦-2を設定しておく
auto dfs = [&](auto &&self, int cur) -> void{
if(edgecnt.at(cur) != 1) return; // 次数2以上からはスタートしない
if(visited.at(cur)) return; // 既に探索したノードも処理しない
group.at(cur) = -2;
visited.at(cur) = true;
for(auto &nxt: g.at(cur)){
if(visited.at(nxt)) continue;
--edgecnt.at(nxt);
self(self, nxt);
}
};
// 次数1のノードを探索
REP(cur, n) dfs(dfs, cur);
// これで、group == -1のノードは閉路を構成する要素になったので、今度は閉路側のノードから全てみる。
// group == -2 がまだどの閉路から出ているかわからないノード
auto dfs2 = [&](auto &&self, int cur, int loopParent) -> void{
if(group.at(cur) == -2) group.at(cur) = loopParent;
for(auto &nxt: g.at(cur)){
if(group.at(nxt) != -2) continue;
self(self, nxt, loopParent);
}
};
// 閉路のノードだった場合、そこから閉路以外のノードを辿る
REP(cur, n){
if(group.at(cur) == -1) dfs2(dfs2, cur, cur);
}
}
void dump_isloop(){
cout << "Namori dump: isloop?" << endl;
REP(i, n){
if(group.at(i) == -1){
cout << " node[" << i << "]: Loop" << endl;
} else{
cout << " node[" << i << "]: group " << group.at(i)<< endl;
}
}
}
};
// https://atcoder.jp/contests/abc266/tasks/abc266_f
void abc266f(){
int n; cin >> n;
Namori namori(n);
REP(i, n){
int u, v; cin >> u >> v;
--u; --v;
namori.makeEdge2Way(u, v);
}
namori.solve();
//namori.dump_isloop();
int m; cin >> m;
REP(i, m){
int u, v; cin >> u >> v;
--u; --v;
// 両方が閉路である場合時計回り、半時計周りがあるのでNo
if(namori.group[u] == -1 && namori.group[v] == -1) cout << "No" << endl;
// 片方が閉路上のノードであるが、もう一方がその閉路から出ている木のノードならYes
else if(namori.group[u] == -1 && namori.group[v] == u) cout << "Yes" << endl;
else if(namori.group[v] == -1 && namori.group[u] == v) cout << "Yes" << endl;
// 両方が(-1ではない)同じ木に所属するならYes
else if(namori.group[u] == namori.group[v]) cout << "Yes" << endl;
// これ以外というのは、閉路上の適当なノードと木のノード、 あるいは、 異なる閉路上のノード上の木なので、
// 閉路上で時計回りと半時計周りを辿れてしまうのでNo
else cout << "No" << endl;
}
}
void test(){
Namori namori(5);
namori.makeEdge2Way(0,1);
namori.makeEdge2Way(1,2);
namori.makeEdge2Way(2,3);
namori.makeEdge2Way(3,4);
namori.makeEdge2Way(1, 3);
namori.solve();
namori.dump_isloop();
}
int main(){
//test();
abc266f();
return 0;
}
参考にしたページ