繁星，夜空，与琉璃题解

省流：

给定 $N×N$ 大小的矩阵，一共 $t$ 秒，每秒会在 $(x,y)$ 的位置出现一个颜色为 $c$ 的星星，颜色 $c$ 是 $R$ 或者 $B$ ，一个或多个相邻的相同颜色的星星构成一个连通块，询问每次新的星星出现之后，当前矩阵中有多少个连通块。

题解：

暴力做法是对于每次出现新的星星的每次查询，使用 $DFS$ 或 $BFS$ 遍历一遍统计全图的连通块的个数，时间复杂度是 $O(t*N^2)$ ，显然会 $TLE$ ，所以考虑并查集。
题目是一个矩阵，二维的并查集并不好维护，所以因为 $N≤10^3$，所以我们可以考虑压维，将二维并查集压成一维，只需要使用一维数组，将下一行接在第一行后面就好，即

int down(int x, int y)
{
    return (x - 1) * n + y;
}

然后我们考虑每增加一颗星星，先默认连通块的数量也就是答案 $+1$，如果能够与周围四格的已有的星星连通，那么再 $-1$ 就好了，剩下的就是常规的一维并查集操作了，时间复杂度是 $ O(\ N^2 + t*α\ (\ N^2\ ))$ ，粗略可以看作 $O(\ N^2\ )$

参考代码：

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

const int MAXN = 1e3 + 10;
int _x[] = { 0, 0, 1, -1 };
int _y[] = { 1, -1, 0, 0 };
int fa[MAXN * MAXN];
int mp[MAXN][MAXN];
int n, t;

int Find(int x)//查找父节点
{
    return fa[x] == x ? x : fa[x] = Find(fa[x]);
}

void merge(int x, int y)//合并两个集合
{
    if (Find(x) != Find(y))
        fa[Find(x)] = Find(y);
}

void init()//初始化并查集
{
    for (int i = 0; i <= n * n; i++)
        fa[i] = i;
}

int down(int x, int y)//压维，坐标转换
{
    return (x - 1) * n + y;//可以画图看一下为什么这么转换
}

signed main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> t;
    init();

    int count = 0;//记录当前有多少片群星，即有多少个集合
    while (t--)
    {
        int x, y, z;
        char c;
        cin >> x >> y >> c;
        if (c == 'R')//转化为数字，好写（不转化也可以）
            z = 1;
        else if (c == 'B')
            z = 2;

        mp[x][y] = z;
        count++;//每次加入一个星星，默认群星数加一

        for (int i = 0; i < 4; i++)//枚举周围四格
        {
            
            int xx = x + _x[i];
            int yy = y + _y[i];
            if (xx<1 || xx>n || yy<1 || yy>n)
                continue;
            if (mp[xx][yy] != z)
                continue;

            int d1 = down(x, y);
            int d2 = down(xx, yy);
            if (Find(d1) != Find(d2))//如果两个集合不相同，合并
            {
                merge(d1, d2);
                count--;//合并后，群星数减一
            }
        }
        cout << count << endl;
    }


    return 0;
}

应某位热心验题人 CoolArec 要求把他的乱搞做法也加上，思路是使用map存点，然后再使用并查集，看个乐就好（

#include<bits/stdc++.h>
using namespace std;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
map<pair<int,int>,pair<int,int>> fa;
map<pair<int,int>,string> mp;

pair<int,int> find(pair<int,int> x){
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,t;
    cin>>n>>t;
    int ans=0;
    while(t--){
        int f=0;
        string s;
        int x,y;cin>>x>>y>>s;
        mp[{x,y}]=s;
        fa[{x,y}]={x,y};
        for(int i=0;i<4;i++){
            int nx=x+dx[i],ny=y+dy[i];
            if(mp[{nx,ny}]!=mp[{x,y}])continue;
            if(find({x,y})==find({nx,ny}))continue;
            if(!f){
                fa[{x,y}]=find({nx,ny});
                f=1;
            }
            else{
                fa[find({x,y})]=find({nx,ny});
                ans--;
            }
        }
        if(!f)ans++;
        cout<<ans<<'\n';
    }
}

$Update：$ 某著名热心验题人 Coolarec 在Codeforces Round 952 H1) 中，使用 map + 并查集来维护连通集，喜提TLE，望周知。
~~（Yuuuki不卡你不代表别人不卡你）~~