#include <stdio.h>
int n, m, i, j, k, a, b, f[105];
int find(int x){
    if(x == f[x]) return x;
    return f[x] = find(f[x]);
}
int main(){
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++) f[i] = i;
    for(i=1; i<=m; i++){
        scanf("%d%d", &a, &b);
        if(find(a) != find(b)){
            f[f[a]] = f[b], n--;
        }//并查集统计连通块,连一条边减少1个 
    }
    printf("%d\n", n);
    return 0;
}

我不会图论也能做:

#include<bits/stdc++.h>
using namespace std;
int n, m, i, j, k, ans, a, b, s[105][105], v[105];
void dfs(int a){
    if(v[a]) return;
    v[a] = 1;//标记统计过 
    for(int b=1; b<=n; b++){
        if(s[a][b]) dfs(b);
    }
}
int main(){
    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++){
        scanf("%d%d", &a, &b);
        s[a][b] = s[b][a] = 1;
    }//这就是所谓的邻接矩阵 
    for(i=1; i<=n; i++){
        if(!v[i]){
            ans++;
            dfs(i);
        }//统计新的连通块 
    }
    printf("%d\n", ans);
    return 0;
}

作者 crxis

发表回复