思路：
并查集的应用。
实现：
1 #include2 #include 3 using namespace std; 4 5 bool a[1005][1005]; 6 int n, x, y; 7 int par[1000005]; 8 int ran[1000005]; 9 int dx[4] = { 1, 0, -1, 0 };10 int dy[4] = { 0, 1, 0, -1 };11 12 void init(int n)13 {14 for (int i = 0; i < n; i++)15 {16 ran[i] = 0;17 par[i] = i;18 }19 }20 21 int find(int x)22 {23 if (par[x] == x)24 return x;25 return par[x] = find(par[x]);26 }27 28 29 void unite(int x, int y)30 {31 x = find(x);32 y = find(y);33 if (x == y)34 return;35 if (ran[x] < ran[y])36 par[x] = y;37 else38 {39 par[y] = x;40 if (ran[x] == ran[y])41 ran[x]++;42 }43 }44 45 bool same(int x, int y)46 {47 return find(x) == find(y);48 }49 50 int trans(int x, int y)51 {52 return x * 1000 + y;53 }54 55 int main()56 {57 init(1000005);58 cin >> n;59 int now = 0, c = 0;60 for (int i = 0; i < n; i++)61 {62 now++;63 c += 4;64 cin >> x >> y;65 a[x][y] = true;66 int tmp = trans(x, y);67 for (int j = 0; j < 4; j++)68 {69 int nx = x + dx[j];70 int ny = y + dy[j];71 if (nx >= 0 && nx < 1000 && ny >= 0 && ny < 1000 && a[nx][ny])72 {73 int t = trans(nx, ny);74 if (!same(tmp, t))75 {76 unite(tmp, t);77 now--;78 }79 c -= 2;80 }81 }82 cout << now << " " << i + 1 << " " << c << endl;83 }84 return 0;85 }