Description

蒜头君来到一个由 n 个小岛组成的世界,岛与岛之间通过修建桥,来让岛上的居民可以去其他的小岛。已知已经修建了 m 座桥,居民们想让蒜头君帮忙计算,最少还要在修建几座桥,居民们才能去所有的岛。

  • 输入格式

第一行输入俩个数字 n,m,分别代表岛的个数,和已经修建的桥的个数,岛的编号分别是\( 1 \ldots n\)。\((1 \leq n \leq 1000, 0 \leq m \leq n \times (n-1) / 2)\)接下来的 m 行,每行俩个数字,代表这俩个编号的岛之间已经有一座桥了。

  • 输出格式

输出最少还需要修建多少座桥,居民才能去所有的岛。

  • 样例输入
1
2
3
4
5
5 4
1 2
2 3
4 5
1 3
  • 样例输出
1
1

Thoughts

连通分量的个数减一,邻接表+dfs处理。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1010;
const int MAX_M = 500000;
int p[MAX_N], eid;
int vis[MAX_N];
int n, m, num = 0;

struct edge {
int v, next;
} E[MAX_M];

void init() {
memset(p, -1, sizeof(p));
memset(vis, 0, sizeof(vis));
eid = 0;
}

void insert(int u, int v) {
E[eid].v = v;
E[eid].next = p[u];
p[u] = eid++;
}

void dfs(int u) {
vis[u] = 1;
//printf("u = %d\n", u);
int i = p[u];
while(i != -1) {
if(vis[E[i].v] == 0)
dfs(E[i].v);
i = E[i].next;
}
}

int main() {
init(); //初始化
scanf("%d %d", &n, &m);
for(int i = 0; i < m; ++i) {
int u, v;
scanf("%d %d", &u, &v);
insert(u, v);
insert(v, u);
}
for(int i = 1; i <= n; ++i) {
if(vis[i] == 0) {
dfs(i);
++num;
}
}
printf("%d\n", num - 1);
return 0;
}

Record

  • 2018年08月23日 完成题解