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