Connect2

 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
#include <stdio.h>
int G[101][101], mark[101], n;
void dfs(int u, int c) {
mark[u]=c;
for(int v=1; v<=n; v++) {
if(G[u][v]==1 && mark[v]!=c && u!=v) {
dfs(v,c);
}
}
}
int main() {
freopen("connect2.in", "r", stdin);
freopen("connect2.out", "w", stdout);
int m, b, e;
scanf("%d %d\n", &n, &m);
if(n==0) {
printf("1");
return 0;
}
if(m==0) {
printf("%d", n);
return 0;
}
for(int i=0; i<101; i++) for(int j=0; j<101; j++) G[i][j]=0;
for(int i=0; i<m; i++) {
scanf("%d %d\n", &b, &e);
if(G[b][e]==0 && G[e][b]==0) {
G[b][e]=1;
G[e][b]=1;
}
}
for(int i=0; i<101; i++) G[i][i]=1;
int count=0, col=1;
for(int i=1; i<=n; i++) {
if(mark[i]==0) {
dfs(i, col++);
count++;
}
}
printf("%d", count);
return 0;
}