B-遥远的回忆

https://ac.nowcoder.com/acm/contest/9033/B

考虑使用并查集
按照题目要求，如果两个块颜色相同，就把他们放入一个并查集
答案就是有多少个并查集

#include<bits/stdc++.h>
using namespace std;
int fa[500005];
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int n,k,ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n+1;i++) fa[i]=i;
    for(int i=1;i<=n;i++){
        scanf("%d",&k);
        if(k&&i<n) fa[find(i)]=find(i+1);
        if(!k&&i>1) fa[find(i)]=find(i-1);
    }
    for(int i=1;i<=n;i++)
        if(find(i)==i)
            ans++;
    cout<<ans<<"\n";
    return 0;
}