ROPER - Biến đổi hoán vị

Tác giả: skyvn97

Ngôn ngữ: C++

#include<stack>
#include<cstdio>
#include<cstring>
#define MAX   100100
using namespace std;
struct vector {
	int d[3];
	int sz;
	vector(){}
	void clear(void) {
		sz=0;
	}
	int size(void) const {
		return (sz);	
	}
	int operator [] (const int &i) const {
		return d[i];
	}
	void push_back(const int &val) {
		sz++;
		d[sz-1]=val;
	}
};
vector g[MAX];
int n,q,nc,cnt;
int p[MAX];
int ncp[MAX];
int low[MAX];
int num[MAX];
bool fr[MAX];
stack<int> st;
void init(void) {
	scanf("%d",&n);
	scanf("%d",&q);
	int i;
	for (i=1;i<=n;i=i+1) {
		scanf("%d",&p[i]);
		g[i].clear();
	}
	for (i=1;i<=n;i=i+1) {
		if (i==1 && p[i]==2) continue;
		if (i==2 && p[i]==1) continue;
		if (i==p[i]) continue;
		g[i].push_back(p[i]);
	}
	g[1].push_back(2);
	g[2].push_back(1);	
}
int min(const int &x,const int &y) {
	if (x<y) return (x); else return (y);
}
void visit(const int &u) {
	int i,v;
	cnt++;
	num[u]=cnt;
	low[u]=cnt;
	st.push(u);
	for (i=0;i<g[u].size();i=i+1) {
		v=g[u][i];
		if (fr[v]) {
			if (num[v]>0) low[u]=min(low[u],num[v]);
			else {
				visit(v);
				low[u]=min(low[u],low[v]);
			}
		}
	}
	if (low[u]==num[u])	{
		nc++;
		do {
			v=st.top();st.pop();
			fr[v]=false;
			ncp[v]=nc;
		}
		while (v!=u);
	}
}
void tarjan(void) {
	memset(low,0,sizeof low);
	memset(num,0,sizeof num);
	memset(fr,true,sizeof fr);
	cnt=0;nc=0;
	int i;
	for (i=1;i<=n;i=i+1)
		if (num[i]==0) visit(i);
}
void answer(void) {
	int i,u,v;
	for (i=1;i<=q;i=i+1) {
		scanf("%d",&u);
		scanf("%d",&v);
		if (ncp[u]==ncp[v]) printf("Yes\n");
		else printf("No\n");
	}
}
int main(void) {
	init();
	tarjan();
	answer();
	return 0;
}

Download