使用并查集解法

通过每次把相同结点的根进行合并,通过使用并查集进行连通块合并,接下来把不同连通块的结点进行下一次合并,一直循环往复,从而获得解

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
const int N = 2e5 + 10;
int a[N],n,s[N],cnt;
int p[N];
bool vis[N];

int find(int x)
{
if(p[x]!=x) p[x] = find(p[x]);
return p[x];
}

void uni(int x,int y)
{
int a = find(x) ; int b = find(y);
if(a!=b)
{
p[a] = b;
}
else return ;
}

int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
p[i] = i;
}

a[0] = -1;
for(int i=1;i<=n;i++)
{
    if(a[i]!=a[i-1]) s[++cnt] = i;
}

int sum = 0;
while(sum < n)
{
    for(int i=1;i<=cnt;i++) cout<<s[i]<<' ';
    cout<<endl;
    //因为不同的果子已经输出,则表明该点与前一个点为不同块 
    for(int i = 1;i<=cnt;i++) uni(s[i]-1,s[i]);
    sum+=cnt;
    int temp = cnt;
    cnt = 0;
    int k = -2;
    for(int i=1;i<=temp;i++)
    {
        int t = find(s[i]) + 1;
        if(t > n) continue;
        if(k!=a[t]) s[++cnt] = t,k=a[t];
    }
}

return 0;

}