Created
June 19, 2016 16:01
-
-
Save tjkendev/1ce0c38486c18a180f83623d74436a5c to your computer and use it in GitHub Desktop.
強連結成分分解 (From AOJ: GRL_3-C Discussion Solution Statistics Submit Connected Components - Strongly Connected Components)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// AC (http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1867905#1) | |
#include<iostream> | |
#include<string> | |
#include<vector> | |
#include<queue> | |
#include<stack> | |
#include<map> | |
#include<set> | |
#include<algorithm> | |
#include<functional> | |
#include<cstdio> | |
#include<cstdlib> | |
#include<cmath> | |
#include<cassert> | |
using namespace std; | |
#define mind(a,b) (a>b?b:a) | |
#define maxd(a,b) (a>b?a:b) | |
#define absd(x) (x<0?-(x):x) | |
#define pow2(x) ((x)*(x)) | |
#define rep(i,n) for(int i=0; i<n; ++i) | |
#define repr(i,n) for(int i=n-1; i>=0; --i) | |
#define repl(i,s,n) for(int i=s; i<=n; ++i) | |
#define replr(i,s,n) for(int i=n; i>=s; --i) | |
#define repf(i,s,n,j) for(int i=s; i<=n; i+=j) | |
#define repe(e,obj) for(auto e : obj) | |
#define SP << " " << | |
#define COL << " : " << | |
#define COM << ", " << | |
#define ARR << " -> " << | |
#define PNT(STR) cout << STR << endl | |
#define POS(X,Y) "(" << X << ", " << Y << ")" | |
#define DEB(A) " (" << #A << ") " << A | |
#define DEBREP(i,n,val) for(int i=0; i<n; ++i) cout << val << " "; cout << endl | |
#define ALL(V) (V).begin(), (V).end() | |
#define INF 1000000007 | |
#define INFLL 10000000000000000007LL | |
#define EPS 1e-9 | |
typedef unsigned int uint; | |
typedef unsigned long ulong; | |
typedef unsigned long long ull; | |
typedef long long ll; | |
typedef long double ld; | |
typedef pair<int, int> P; | |
//typedef pair<ll, ll> P; | |
typedef pair<P, int> PI; | |
typedef pair<int, P> IP; | |
typedef pair<P, P> PP; | |
typedef priority_queue<P, vector<P>, greater<P> > pvqueue; | |
#define V 10003 | |
#define E 30003 | |
int v; | |
vector<int> g[V]; | |
vector<int> rg[V]; | |
vector<int> ord; | |
bool used[V]; | |
int group[V]; | |
// 1回目のDFS | |
// 辺を使って探索し、戻り順に(探索順の)番号をつけていく | |
void dfs(int s) { | |
used[s] = true; | |
rep(i, g[s].size()) { | |
int t = g[s][i]; | |
if(!used[t]) { | |
dfs(t); | |
} | |
} | |
ord.push_back(s); | |
} | |
// 2回目のDFS | |
// 逆辺を辿ってたどり着ける頂点には同じ番号をつける | |
void rdfs(int s, int col) { | |
group[s] = col; | |
used[s] = true; | |
rep(i, rg[s].size()) { | |
int t = rg[s][i]; | |
if(!used[t]) { | |
rdfs(t, col); | |
} | |
} | |
} | |
// 強連結成分分解 | |
int strongly_connected_components() { | |
rep(i, v) used[i] = false; | |
rep(i, v) { | |
if(!used[i]) dfs(i); | |
} | |
rep(i, v) used[i] = false; | |
assert(ord.size() == v); | |
int cnt = 0; | |
// 2回目のDFSは番号の逆順に行う | |
repr(i, v) { | |
int s = ord[i]; | |
if(!used[s]) rdfs(s, cnt++); | |
} | |
return cnt; | |
} | |
int main() { | |
int e; | |
cin >> v >> e; | |
rep(i, e) { | |
int s, t; | |
cin >> s >> t; | |
g[s].push_back(t); | |
rg[t].push_back(s); | |
} | |
strongly_connected_components(); | |
int q; | |
cin >> q; | |
rep(_, q) { | |
int u, v; | |
cin >> u >> v; | |
cout << (group[u] == group[v] ? 1 : 0) << endl; | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment