給定一個長度為 N 的數組 A=[A1,A2,???AN]，數組中有可能有重復出現的整數。
現在小明要按以下方法將其修改為沒有重復整數的數組。
小明會依次修改 A2,A3,???,AN。
當修改 Ai 時，小明會檢查 Ai 是否在 A1～Ai?1 中出現過。
如果出現過，則小明會給 Ai 加上 1；如果新的 Ai 仍在之前出現過，小明會持續給 Ai 加 1，直到 Ai 沒有在 A1～Ai?1 中出現過。
當 AN 也經過上述修改之后，顯然 A 數組中就沒有重復的整數了。
現在給定初始的 A 數組，請你計算出最終的 A 數組。

輸入格式
第一行包含一個整數 N。
第二行包含 N 個整數 A1,A2,???,AN。

輸出格式
輸出 N 個整數，依次是最終的 A1,A2,???,AN。

數據范圍
1≤N≤105,
1≤Ai≤106
輸入樣例：
5
2 1 1 3 4
輸出樣例：
2 1 3 4 5

代碼如下：

#include <iostream> using namespace std; const int N = 1000010; int a[N]; int find(int x) {if (a[x]!=x) a[x] = find(a[x]);return a[x]; }int main() {int n;cin>>n;for (int i = 1;i<=N;i++) a[i] = i;for (int i = 1;i<=n;i++){int x;cin>>x;x = find(x);cout<<a[x]<<" ";a[x] = x+1;}return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的单链表式并查集应用举例的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。