旅行

C++11(clang++ 3.9) 解法, 执行用时: 1291ms, 内存消耗: 49424K, 提交时间: 2020-08-05 16:53:17

#include<bits/stdc++.h>
using namespace std;
const int maxn=200009;

int n,m,T;
vector<int>G[maxn];

int siz[maxn];

int stk[maxn],top;
int dfsclock,scccnt;
int pre[maxn],lowlink[maxn],sccno[maxn];
void dfs(int u){
	pre[u]=lowlink[u]=++dfsclock;
	stk[++top]=u;
	for(int i=0;i<G[u].size();++i){
		int v=G[u][i];
		if(!pre[v]){
			dfs(v);
			lowlink[u]=min(lowlink[u],lowlink[v]);
		}else if(!sccno[v]){
			lowlink[u]=min(lowlink[u],pre[v]);
		}
	}
	
	if(lowlink[u]==pre[u]){
		++scccnt;
		for(;;){
			int x=stk[top--];
			sccno[x]=scccnt;
			if(x==u)break;
		}
	}
}

vector<int>G2[maxn];
int vis[maxn];

const int B=1000;
bitset<B+9>f[100009];
void dfs2(int x){
	if(vis[x])return;
	vis[x]=1;
	for(int i=0;i<G2[x].size();++i){
		int v=G2[x][i];
		dfs2(v);
		f[x]|=f[v];
	}
}


unordered_set<int>K[maxn];
int read(){
	int r=0,k=1;
	char c=getchar();
	for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;
	for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';
	return r*k;
}

int qx[2*maxn],qy[2*maxn];
int ans[2*maxn];
int main(){
	scanf("%d%d",&n,&m);
	while(m--){
		int x=read()+1,y=read()+1;
		G[x].push_back(y);
	}
	for(int i=1;i<=n;++i)if(!pre[i])dfs(i);
	for(int i=1;i<=n;++i){
		for(int j=0;j<G[i].size();++j){
			int v=G[i][j];
			if(sccno[i]!=sccno[v]&&!K[sccno[i]].count(sccno[v])){
				G2[sccno[i]].push_back(sccno[v]);
				K[sccno[i]].insert(sccno[v]);
			}
		}
	}
	
	scanf("%d",&T);
	
	for(int i=1;i<=T;++i){
		qx[i]=sccno[read()+1];qy[i]=sccno[read()+1];
	}
	for(int k=0;;++k){
		if(k*B+1>scccnt)break;
		for(int i=1;i<=scccnt;++i){
			f[i].reset();vis[i]=0;
		}
		for(int i=1;i<=B;++i)f[k*B+i].set(i,1);
		for(int i=1;i<=scccnt;++i)dfs2(i);
		for(int i=1;i<=T;++i){
			if(qy[i]<=k*B||qy[i]>(k+1)*B)continue;
			int t=qy[i]-B*k;
			if(f[qx[i]][t])ans[i]=1;else ans[i]=0;
		}
	}
	for(int i=1;i<=T;++i){
		if(ans[i]){
			printf("Good\n");
		}else{
			printf("Bad\n");
		}
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 614ms, 内存消耗: 21300K, 提交时间: 2020-08-06 17:56:34

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
const int N = 1e5 + 5, M = 405;
vector<int> G[N], DAG[N];
vector<pii> edges;
int n, m, _;
int dfn[N], num[N], low[N], id, tot, sta[N], top, deg[N], idx[N];
bool in[N];
int vis[N], spe[N];
bitset<N> bit[M];
void tarjan(int u)
{
	in[u] = 1;
	low[u] = dfn[u] = ++id;
	sta[++top] = u;
	for(int v : G[u])
	{
		if(!dfn[v])
		{
			tarjan(v);
			low[u] = min(low[u],low[v]);
		}
		else if(in[v]) low[u] = min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u])
	{
		tot++;
		while(top)
		{
			int tmp = sta[top--];
			in[tmp] = 0;
			num[tmp] = tot;
			if(tmp==u) break;
		}
	}
}
void dfs(int u, int t)
{
	if(spe[u]) { bit[t] |= bit[spe[u]]; return; }
	vis[u] = t;
	bit[t].set(u);
	for(int v : DAG[u])
	{
		if(vis[v]==t) continue;
		dfs(v, t);
	}
}
void prework()
{
	for(int i=1; i<=n; i++)
		if(!dfn[i]) tarjan(i);
	for(auto it : edges)
	{
		int u = num[it.fi], v = num[it.se];
		if(u!=v) DAG[u].pb(v), deg[u]++, deg[v]++;
	}
	int lim = (int)sqrt(tot) + 1;
	iota(idx+1, idx+tot+1, 1);
	sort(idx+1, idx+tot+1, [](int x, int y) {
		return deg[x] > deg[y];
	});
	for(int i=1; i<=lim; i++) 
	{
		dfs(idx[i], i);
		spe[idx[i]] = i;
	}
}
bool dfs2(int s, int t, int tt)
{
	if(s==t) return 1;
	if(spe[s]) return bit[spe[s]].test(t);
	vis[s] = tt;
	for(int ss : DAG[s])
	{
		if(vis[ss]==tt) continue;
		if(dfs2(ss, t, tt)) return 1;
	}
	return 0;
}
void solve(int t)
{
	int u, v;
	scanf("%d%d", &u, &v);
	++u, ++v;
	if(num[u]==num[v]) puts("Good");
	else puts((dfs2(num[u], num[v], t) ? "Good" : "Bad"));
}
int main()
{
	scanf("%d%d", &n, &m);
	for(int i=1; i<=m; i++) 
	{
		int u, v;
		scanf("%d%d", &u, &v);
		++u, ++v;
		G[u].pb(v);
		edges.emplace_back(u, v);
	}
	prework();
	scanf("%d", &_);
	for(int i=1; i<=_; i++) solve(400+i);
	return 0;
}

详情