紫书 习题 11-12 UVa 1665 （并查集维护联通分量）

这道题要逆向思维

反过来从大到小枚举， 就是在矩阵中一点一点加进去数字，这样比较

好操作， 如果正着做就要一点一点删除数字， 不好做。

我们需要在这个过程中维护联通块的个数， 这里用到了并查集。

首先加进去一个数， 联通分量数字先加一， 然后再考虑有没有和其他联通分量

相连。从当前位置四个方向枚举， 如果这个数之前已经被选中， 同时

不是一个联通分量， 那么也就是说当前这个木块把两个联通分量变成一个

联通分量， 联通分量数减去一。

这里还要把二维的化为一维的编号， 方便并查集操作。

然后注意这里输出很奇怪， 最后输出一行的最后一个位置是要有空格的

不然会格式错误。

#include<cstdio>

#include<vector>

#include<cstring>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 1123456;

struct node

{

	int x, y, v;

	bool operator < (const node& rhs) const

	{

		return v < rhs.v;

	}

};

vector<node> nodes;

int a[MAXN], ans[MAXN], n, m, k, sum;

int vis[MAXN], f[MAXN];

int dir[4][2] = {0, 1, 0, -1, -1, 0, 1, 0};

int find(int x)

{

	if(f[x] != x)

		f[x] = find(f[x]);

	return f[x];

}

inline int ID(int x, int y) { return x * m + y; } //二维化一维

void add(node u)

{

	sum++;

	vis[ID(u.x, u.y)] = 1;

	REP(i, 0, 4) //判断是否和其他联通分量相连

	{

		int xx = u.x + dir[i][0], yy = u.y + dir[i][1];

		if(0 <= xx && xx < n && 0 <= yy && yy < m && vis[ID(xx, yy)]) //vis的作用是之前这个数有没有被选过

		{

			int a = find(ID(u.x, u.y)), b = find(ID(xx, yy));

			if(a != b) sum--, f[a] = b;

		}

	}

}

int main()

{

	int T;

	scanf("%d", &T);

	while(T--)

	{

		memset(vis, 0, sizeof(vis));

		nodes.clear();

		scanf("%d%d", &n, &m);

		REP(i, 0, n)

			REP(j, 0, m)

			{

				int v;

				scanf("%d", &v);

				nodes.push_back(node{i, j, v});

			}

		scanf("%d", &k);

		REP(i, 0, k) scanf("%d", &a[i]);

		sort(nodes.begin(), nodes.end()); //把点排序，这样加数比较方便

		REP(i, 0, n * m) f[i] = i;

		int pos = nodes.size() - 1; sum = 0;

		for(int i = k - 1; i >= 0; i--)

		{

			while(nodes[pos].v > a[i])

				add(nodes[pos--]);

			ans[i] = sum;

		}

		REP(i, 0, k) printf("%d ", ans[i]); //注意最后一个数字后要有空格

		printf("\n");

	}

	return 0;

}