把相关联的两个点记下来,然后dfs.这个题n是5*10^4,无法开一个num[n][n]的二维数组,但是了可以用vector
#include<cstdio> #include<iostream> #include<cstring> #include<vector> #include<algorithm> #define MAXN 50010 using namespace std; vector<int>st[MAXN]; int n,r1,r2,ans[MAXN],vis[MAXN]; void dfs(int cur) { if(vis[cur]) return ; vis[cur]=true; for(int i=0; i<(int)st[cur].size(); i++) { int a=st[cur][i]; if(vis[a]) continue; ans[a]=cur; dfs(a); } } int main() { //freopen("in.txt","r",stdin); cin>>n>>r1>>r2; for(int i=1; i<=n; i++) { if(i==r1) continue; int a; cin>>a; st[a].push_back(i); st[i].push_back(a); } memset(ans,0,sizeof(ans)); memset(vis,false,sizeof(vis)); dfs(r2); int flag=0; for(int i=1; i<=n; i++) { if(i==r2) continue; if(flag) cout<<" "; cout<<ans[i]; flag=1; } cout<<endl; return 0; }