首页 > 代码库 > CodeForces 698B Fix a Tree （并查集应用）
CodeForces 698B Fix a Tree （并查集应用）
当时也是想到了并查集，但是有几个地方没有想清楚，所以就不知道怎么写了，比如说如何确定最优的问题。赛后看了一下别人的思路，才知道自己确实经验不足，思维也没跟上。
其实没有那么复杂，这个题目我们的操作只有三个 1、确定根节点。2、解环。 3连接子树。
如果题目中给出了一个或者多个根节点，我们任选一个即可，证明：假设有k个可行根节点，那么选择一个不动，改动k-1次，每种选择都是这样。但如果题目中没有可选根节点，就不可以随便去选了，首先明确这种情况一定存在了1个或者多个环，我们一定要从环中选取根节点，因为这样只进行了一次操作就破环了环结构而且确定了根节点，如果在环外选择根节点，则改动为根节点需要1步，解环也需要一步，不是最优解！
为了操作方便，使用并查集寻找环，并将找到第一个环的任意一个节点作为根节点。
在确定了根节点之后，如果遇到其他可行根节点，直接连接到已确定根节点即可，就是连接子树的操作。
注意：这个注意是对我自己说的，我犯了一个低级错误，我在判断环的时候居然没有用find判断，而是用fa判断，当时还感觉很困惑，以为合并方式不对，发现了以后才感觉自己真是好久没做过并查集了。。
代码如下：
#include<iostream>#include<cstdio>#include<cstring>using namespace std;#define N 200020int a[N],fa[N];int Find(int x){ return x==fa[x] ? x : fa[x] = Find(fa[x]);}void unin(int x,int y){ int fax = Find(x); int fay = Find(y); fa[fay] = fax;}int main(){ int root = -1,ans=0,n; cin>>n; for(int i = 1; i <= n; i++) { cin>>a[i]; fa[i] = i; if(a[i]==i) root = i; } for(int i = 1; i <= n; i++) { if(i == a[i] && a[i] == root) continue; else if(a[i] == i && i != root) { a[i] = root; ans++; unin(root,i); } else if(a[i] != i && Find(a[i]) != Find(i)) { unin(a[i],i); } else if(a[i] != i && Find(a[i]) == Find(i)) { ans++; if(root == -1) { root = i; } a[i] = root; unin(root,i); } } cout<<ans<<endl; for(int i = 1; i <= n; i++) { if(i==n) cout<<a[i]<<endl; else cout<<a[i]<<" "; } return 0;}
CodeForces 698B Fix a Tree （并查集应用）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。