我们用并查集来保证留下的边组成的是一棵生成树,然后按拓扑排序进行遍历(不会破坏已经排好的点)
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 1010,M = N*N;
int P[N];
int fa[N];
int n,m;
int h[N],e[M],w[M],ne[M],idx;
int d[N];
int find(int x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
void add(int a,int b,int c){
e[++idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>P[i];
fa[i] = i;
}
vector<vector<PII>> G;
cin>>m;
for(int i=1;i<=m;i++){
int a,b;cin>>a>>b;
if(find(a)==find(b))continue;
fa[find(a)] = find(b);
add(a,b,i);add(b,a,i);
d[a]++;d[b]++;
}
queue<int> Q;
for(int i=1;i<=n;i++)
if(d[i]<=1)Q.push(i);
vector<int> ans;
while(Q.size()){
int t = Q.front();Q.pop();
vector<int> pi(n+1),p(n+1),st(n+1);//存父节点的编号和边的编号
queue<int> q;
q.push(t);
st[t] = 1;
while(q.size()){//求t到所有点的路径
int u = q.front();
q.pop();
for(int i=h[u];i;i=ne[i]){
int j = e[i];
int id = w[i];
if(!st[j]){
st[j] = 1;
pi[j] = id;
p[j] = u;
q.push(j);
}
}
}
int s = 0;
for(int i=1;i<=n;i++)
if(P[i]==t)
s = i;//t的P中的位置
if(s != t && p[s] == 0){//s不能到t
puts("-1");
return 0;
}
//注意我们是按照拓扑排序执行的,对应到生成树上就是从叶节点开始复位
//这样我们走过的路程是不会影响已经恢复的点的
while(s!=t){
ans.push_back(pi[s]);
swap(P[s],P[p[s]]);
s = p[s];
}
for(int i=h[t];i;i=ne[i]){
int j = e[i];
if(--d[j]==1)Q.push(j);
}
}
cout<<ans.size()<<endl;
for(int x : ans)cout<<x<<" ";
cout<<endl;
}