题意：
给出n个点的父节点，问最少修改几个点能使整个图变成一棵树。
题解：
给出的图可能包括多个树、环，要使图变成树则要先将环解开，再将树合并。
用并查集保存树，再通过dfs判断是否存在环，解开环要注意一些细节。
#include<iostream> #include <stdio.h> #include <algorithm> #include <math.h> #include<stdlib.h> #include <string.h> #include<queue> #include<set> #include<map> #include<stack> #include<time.h> using namespace std; #define MAX_N 200005 #define inf 0x7fffffff #define LL long long #define ull unsigned long long #define mod 10007 LL INF=9e18; int n; int par[MAX_N]; int ans[MAX_N]; vector<int>G[MAX_N]; int find(int x) { return x==par[x]?x:par[x]=find(par[x]); } void unite(int x,int y) { x = find(x); y = find(y); par[x] = y; } void init() { for(int i=1;i<=n;i++) par[i] = i; } bool dfs(int u,int v,int s) { for(int i=0;i<G[u].size();i++) { if(G[u][i] == s || G[u][i] == v) { return true; } else { if(dfs(G[u][i], u, s)) return true; } } return false; } int main() { cin >> n; init(); for(int i=1;i<=n;i++) { int fa; scanf("%d",&fa); if(i != fa) G[i].push_back(fa); ans[i] = fa; unite(i, fa); } int cnt = -1; int fa; int Fa = 0; for(int i=1;i<=n;i++) { if(par[i] == i) { cnt++; fa = i; if(!dfs(i, 0, i)) Fa = i; } } if(!Fa) { cnt++; ans[fa]=fa; } else { fa = Fa; } for(int i=1;i<=n;i++) { if(par[i] == i && i != fa) { ans[i] = fa; par[i] = fa; } } cout << cnt << endl; for(int i=1;i<=n;i++) { printf("%d%c",ans[i],i==n?'\n':' '); } }
