[Codeforces] 698B. Fix a Tree
題目連結:http://codeforces.com/problemset/problem/698/B
一開始完全沒想法,被提示(?說就算非法也還是一張圖後才比較有想法。這題我的作法很greedy,就先判斷一下有沒有原本就有可以當根的點,有的話就把他當根,接下來再掃一遍,看看有沒有人會構成環,有的話就直接把他接到根上面,此外,若沒有現成的根的話就直接把他變成根。而要找誰跟誰一樣就用個並查集就好了XD
一開始完全沒想法,被提示(?說就算非法也還是一張圖後才比較有想法。這題我的作法很greedy,就先判斷一下有沒有原本就有可以當根的點,有的話就把他當根,接下來再掃一遍,看看有沒有人會構成環,有的話就直接把他接到根上面,此外,若沒有現成的根的話就直接把他變成根。而要找誰跟誰一樣就用個並查集就好了XD
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define FF first
#define SS second
const int N = 200000 + 5;
class DJS{
private:
vector<int> arr;
public:
void init(int n){
arr.resize(n);
for(int i=0;i<n;i++) arr[i]=i;
}
int query(int x){
if(arr[x]!=x) arr[x] = query(arr[x]);
return arr[x];
}
void merge(int a, int b){
arr[query(a)]=arr[query(b)];
}
} djs;
int arr[N];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n, ans = 0, root = -1; cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
if(arr[i]==i and root==-1) root=i;
}
djs.init(n+1);
for(int i=1;i<=n;i++){
int x = arr[i];
if(x == root) continue;
if(djs.query(x) == djs.query(i)){
if(root == -1){
root = i;
if(x!=i){
x=i;
ans++;
}
}else{
djs.merge(i, root);
x = root;
ans++;
}
}else djs.merge(x, i);
arr[i] = x;
}
if(root == -1){
arr[1]=1;
ans++;
}
cout<<ans<<'\n';
for(int i=1;i<=n;i++) cout<<arr[i]<<" \n"[i==n];
return 0;
}
留言
張貼留言