ABC288C生成树——连通块变森林

多个连通块，要求没有环，至少删除多少条边？成环的边不要即可。

#include <stdio.h>
int n, m, i, j, k, a, b, f[200050];
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)) k++;//成环删边
        else f[f[a]] = f[b];//边留下合并
    }
    printf("%d\n", k);
    return 0;
}

没学并查集也能做：

#include <stdio.h>
#define N 200050
int n, m, i, j, k, a, b, c, s, h[N], v[N];
struct AB{
    int a, b, n;
} d[N*2];
void cun(int a, int b){
    d[++k].a = a, d[k].b = b;
    d[k].n = h[a], h[a] = k;
}
void dfs(int a){
    int b, i;
    if(v[a]) return;
    v[a] = ++c;
    for(i=h[a]; i; i=d[i].n) dfs(d[i].b);
}
int main(){
    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++){
        scanf("%d%d", &a, &b);
        cun(a, b);
        cun(b, a);
    }
    for(i=1; i<=n; i++){
        if(!v[i]){
            c = 0;
            dfs(i);
            s += c - 1;
        }//每个连通块保留c-1条边
    }
    printf("%d\n", m-s);
    return 0;
}