显示代码纯文本
/*
（Brian Dean分析）
此问题是一种递归（深度优先）搜索以识别图形中的连接组件的练习。
第一项任务比第二项任务简单得多。我们建一个图，其中每个单元格是一个节点，如果它们包含相同的数字，则两个相邻的单元格连接一条边。
然后，我们从每个单元格开始递归填充（跳过已经访问过的单元格），扩展每个联通区域，并累加联通区域的大小。
我的下面的代码实际上做了一些略微不同的事情 - 但它最终是等价的 - 通过为每个不同的ID号创建一个单独的图，
然后递归搜索所有这些（这允许我在解决任务2时可很大程度上重用任务1的代码）。
对于第二项任务，我们为每对奶牛（x，y）创建一个图，节点是我们在第一个任务中计算的区域，用一条边连接相邻区域，
其中一个区域由牛x标记，另一个区域由牛y标记。
给图中的每个节点一个“权”值，其权值与第一个任务的相应区域的大小相同。
然后我们在每个图形上开始递归填充以找到具有最大面积的任何一个。
这里有两个重要的想法可以使我们的解决方案快速运行。
一种方法是确保第一个任务中的每个区域都压缩到第二个任务中的单个节点。如果我们不这样做，那么在第二个任务中，
我们可能会一遍又一遍地递归扫描相同的大区域，浪费了相当多的时间。
另一个方法是，当我们进行递归搜索时，我们需要确保运行时间仅依赖于图中的边数而不是节点数，
因为每个（x，y）牛对图是涉及大量Node的第二个任务，但可能只有少数边。
例如，我们不希望为每个节点保留一个“是否遍历过”的标记数组，并且在每个递归搜索时都被初始化为false。
相反，在下面的解决方案中，我们为此使用了映射数据结构，它只在需要时创建标志，避免初始化不相关节点的初始化标志。
每个数字块是一个整体，用并查集维护大小 。
给所有相邻数字块建边 ，并根据颜色排序
处理每个数字块与那些数字块相连，维护一个颜色连接着哪些数字块。
枚举处理所有相邻的数字块方案，已经根据数字值安排在一起。
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <vector>
#include<numeric>
using namespace std;
struct Edge {
int u, v, c1, c2;
Edge() {}
Edge(int u, int v, int c1, int c2) : u(u), v(v), c1(min(c1, c2)), c2(max(c1, c2)) {}
bool operator<(const Edge& rhs) const {
if (c1 != rhs.c1)
return c1 < rhs.c1;
return c2 < rhs.c2;
}
};
const int N = 252;
int n, ecnt;
int f[N * N], sz[N * N], szcp[N * N];
int a[N][N];
Edge ed[N * N * 2];
vector<int> sts[1000010];
int find(int x);
int gind(int x, int y);
void merge(int x, int y);
int main() {
freopen("multimoo_silver_18open.in","r",stdin);
freopen("multimoo_silver_18open.out","w",stdout);
int a1 = 0, a2 = 0;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
scanf("%d", &a[i][j]);
for(int i=1; i<=n*n; i++) f[i]=i;
for(int i=1; i<=n*n; i++) sz[i]=1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {//向右下方合并相同的区域
if (i != n && a[i][j] == a[i + 1][j])
merge(gind(i, j), gind(i + 1, j));
if (j != n && a[i][j] == a[i][j + 1])
merge(gind(i, j), gind(i, j + 1));
a1 = max(a1, sz[find(gind(i, j))]);//合并的过程中找最大值
}
}
for (int i = 1; i <= n; ++i)//再扫描一遍，找相邻的两个区域
for (int j = 1; j <= n; ++j) {
if (i != n && a[i][j] != a[i + 1][j]) {//建右侧边 ，二维坐标转换为一维数字。
ed[++ecnt] = Edge(find(gind(i, j)), find(gind(i + 1, j)), a[i][j], a[i + 1][j]);
}
if (j != n && a[i][j] != a[i][j + 1]) {//建下方边
ed[++ecnt] = Edge(find(gind(i, j)), find(gind(i, j + 1)), a[i][j], a[i][j + 1]);
}
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
int ind = gind(i, j);
if (find(ind) == ind)//以颜色为节点，当前颜色连接着那些块
sts[a[i][j]].push_back(ind);
}
sort(ed + 1, ed + ecnt + 1);
memcpy(szcp, sz, sizeof(sz));
for (int i = 1; i <= ecnt; ) {//处理边，也就是这些相邻块
int c1 = ed[i].c1, c2 = ed[i].c2;//排序后的相邻颜色已经在一起
while (ed[i].c1 == c1 && ed[i].c2 == c2) {//处理在一起的这些颜色
merge(ed[i].u, ed[i].v);
a2 = max(a2, sz[find(ed[i].u)]);
++i;
}//处理完一种颜色匹配后，状态恢复，以备处理另一种颜色。
for (int j=0; j<sts[c1].size(); j++) {
int u=sts[c1][j];
f[u] = u;
sz[u] = szcp[u];
}
for (int j=0; j<sts[c2].size(); j++) {
int u=sts[c2][j];
f[u] = u;
sz[u] = szcp[u];
}
}
printf("%d\n%d\n", a1, a2);
return 0;
}
inline int gind(int x, int y) {
return (x - 1) * n + y;
}
int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y)
return;
sz[x] += sz[y];
f[y] = x;
}
yuan