用户输出
2系统信息
Exited with return code 0| 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| #48980 | #1257. 车 | Accepted | 100 | 186 ms | 4328 K | C++ 17 / 1.6 K | XYZ | 2021-05-19 23:57:44 |
#include <bits/stdc++.h>
#define MAX_M 1000
#define ii pair<int, int>
using namespace std;
ii coords[MAX_M];
map<ii, int> rcds;
int parent[MAX_M];
int find(int x) {
if (parent[x] > 0)
parent[x] = find(parent[x]); //递归查找，同时起到了压缩路径的作用
return parent[x] > 0 ? parent[x] : x; //返回父亲节点，根节点返回自身
}
void union_set(int x, int y) {
x = find(x), y = find(y); //查找父亲节点
if (x != y) //合并时不能是相同父亲节点的
{
if (parent[x] < parent[y]) //比较大小，小的连到大的上
{
parent[x] += parent[y];
parent[y] = x;
} else {
parent[y] += parent[x];
parent[x] = y;
}
}
}
int main() {
int n;
int m;
cin >> n >> m;
vector<vector<int> > board(n, vector<int>(n));
for (int i = 0; i < m; i++) {
int x, y;
scanf("%d %d", &x, &y);
x--;
y--;
board[x][y] = 1;
ii xy = make_pair(x, y);
coords[i] = xy;
rcds[xy] = i;
}
memset(parent, -1, sizeof(parent));
for (int i = 0; i < m; i++) {
ii xy = coords[i];
int x = xy.first;
int y = xy.second;
for (int j = y + 1; j < n; j++) {
if (board[x][j]) {
union_set(i, rcds[ii(x, j)]);
}
}
for (int j = x + 1; j < n; j++) {
if (board[j][y]) {
union_set(i, rcds[ii(j, y)]);
}
}
}
set<int> res;
for (int i = 0; i < m; i++) {
res.insert(find(i));
}
int ans = m - res.size();
printf("%d", ans);
return 0;
}用户输出
8系统信息
Exited with return code 0用户输出
9系统信息
Exited with return code 0用户输出
12系统信息
Exited with return code 0用户输出
12系统信息
Exited with return code 0用户输出
17系统信息
Exited with return code 0用户输出
17系统信息
Exited with return code 0用户输出
16系统信息
Exited with return code 0用户输出
14系统信息
Exited with return code 0901 598
565 361
500 175
205 860
524 404
193 20
190 212
379 254
654 653
174 763
344 42
271 140
76 774
<4567 bytes omitted>用户输出
330系统信息
Exited with return code 0530 551
370 236
26 367
405 200
55 355
436 316
478 344
397 315
476 392
60 512
233 526
514 248
429 325
<4086 bytes omitted>用户输出
396系统信息
Exited with return code 0904 84
121 471
711 121
862 151
441 193
514 539
479 427
342 129
583 269
260 175
607 462
641 578
282 2
<560 bytes omitted>用户输出
2系统信息
Exited with return code 0322 197
178 243
39 189
83 306
293 89
254 60
223 82
96 176
262 302
276 15
135 248
265 232
63 281
179
<1356 bytes omitted>用户输出
91系统信息
Exited with return code 0569 804
264 153
179 489
204 404
121 227
309 101
534 470
361 276
537 107
474 107
513 334
167 332
313
<6023 bytes omitted>用户输出
729系统信息
Exited with return code 0254 526
54 106
142 201
49 219
238 117
136 242
171 196
132 49
59 44
195 169
103 230
222 77
154 159
14
<3680 bytes omitted>用户输出
511系统信息
Exited with return code 0300 844
197 204
168 265
277 270
101 251
192 36
222 79
270 212
242 139
161 124
169 220
182 249
177 25
<6051 bytes omitted>用户输出
839系统信息
Exited with return code 0503 668
81 343
481 83
182 390
22 300
487 210
278 503
164 337
90 1
437 244
219 20
98 97
210 262
76 42
<5008 bytes omitted>用户输出
577系统信息
Exited with return code 0300 848
273 182
240 132
279 174
237 281
279 180
131 34
24 238
239 8
274 237
63 24
79 233
204 105
75
<6055 bytes omitted>用户输出
841系统信息
Exited with return code 0166 728
126 14
151 109
118 126
112 37
76 151
6 71
98 94
117 79
101 90
84 42
117 112
42 7
54 6
155 98
<4795 bytes omitted>用户输出
727系统信息
Exited with return code 07 49
1 1
1 2
1 3
1 4
1 5
1 6
1 7
2 1
2 2
2 3
2 4
2 5
2 6
2 7
3 1
3 2
3 3
3 4
3 5
3 6
3 7
4 1
4 2
4 3
<101 bytes omitted>用户输出
48系统信息
Exited with return code 015 225
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
2 1
2 2
2 3
2 4
2 5
2 6
2 7
<987 bytes omitted>用户输出
224系统信息
Exited with return code 026 676
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1
<3495 bytes omitted>用户输出
675系统信息
Exited with return code 031 961
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1
<5115 bytes omitted>用户输出
960系统信息
Exited with return code 0666 999
1 1
1 2
2 2
4 3
3 4
4 4
5 5
6 5
6 6
7 7
8 7
7 8
9 9
9 10
10 10
12 11
11 12
12 12
13 13
14 13
<7576 bytes omitted>用户输出
666系统信息
Exited with return code 0666 999
2 1
1 2
2 2
4 3
3 4
4 4
5 5
6 5
6 6
8 7
7 8
8 8
9 9
10 9
9 10
12 11
11 12
12 12
13 13
14 13
<7576 bytes omitted>用户输出
666系统信息
Exited with return code 0666 999
2 1
1 2
2 2
3 3
4 3
4 4
6 5
5 6
6 6
7 7
7 8
8 8
9 9
10 9
10 10
11 11
11 12
12 12
13 13
14 13
<7576 bytes omitted>用户输出
666系统信息
Exited with return code 0666 999
2 1
1 2
2 2
3 3
4 3
3 4
5 5
6 5
5 6
8 7
7 8
8 8
9 9
10 9
10 10
11 11
11 12
12 12
13 13
14 13
<7575 bytes omitted>用户输出
666系统信息
Exited with return code 0666 999
2 1
1 2
2 2
3 3
3 4
4 4
5 5
6 5
6 6
7 7
7 8
8 8
9 9
10 9
10 10
11 11
11 12
12 12
13 13
14 13
<7576 bytes omitted>用户输出
666系统信息
Exited with return code 0666 999
1 1
1 2
2 2
3 3
4 3
4 4
5 5
5 6
6 6
7 7
8 7
8 8
9 9
10 9
9 10
11 11
11 12
12 12
14 13
13 14
<7575 bytes omitted>用户输出
666系统信息
Exited with return code 0666 999
1 1
2 1
2 2
3 3
3 4
4 4
6 5
5 6
6 6
7 7
8 7
8 8
9 9
10 9
10 10
11 11
12 11
12 12
13 13
14 13
<7577 bytes omitted>用户输出
666系统信息
Exited with return code 0666 999
1 1
2 1
1 2
3 3
4 3
3 4
5 5
5 6
6 6
7 7
7 8
8 8
9 9
10 9
10 10
11 11
12 11
11 12
13 13
13 14
<7575 bytes omitted>用户输出
666系统信息
Exited with return code 0666 999
2 1
1 2
2 2
3 3
4 3
3 4
5 5
5 6
6 6
8 7
7 8
8 8
9 9
10 9
10 10
11 11
12 11
12 12
13 13
14 13
<7576 bytes omitted>用户输出
666系统信息
Exited with return code 0666 999
2 1
1 2
2 2
3 3
4 3
3 4
5 5
6 5
5 6
7 7
8 7
7 8
9 9
10 9
9 10
12 11
11 12
12 12
13 13
13 14
<7575 bytes omitted>用户输出
666系统信息
Exited with return code 0用户输出
9系统信息
Exited with return code 0用户输出
9系统信息
Exited with return code 0100 100
1 55
2 55
3 55
4 55
5 55
6 55
7 55
8 55
9 55
10 55
11 55
12 55
13 55
14 55
15 55
16 55
17 55
<500 bytes omitted>用户输出
99系统信息
Exited with return code 0100 100
81 1
81 2
81 3
81 4
81 5
81 6
81 7
81 8
81 9
81 10
81 11
81 12
81 13
81 14
81 15
81 16
81 17
<500 bytes omitted>用户输出
99系统信息
Exited with return code 01000 1000
1 608
2 608
3 608
4 608
5 608
6 608
7 608
8 608
9 608
10 608
11 608
12 608
13 608
14 608
1
<7803 bytes omitted>用户输出
999系统信息
Exited with return code 0