n个点,m条边,根据红蓝规则连边,最终有多少个连通块不是环,有多少个是环?
所谓红蓝边规则,就是每个点的一段只会连接1次!按照这个规则,颜色都不需要读入了!

#include <stdio.h>
int n, m, i, j, k, a, b, x, y, f[200005];
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%*s%d%*s", &a, &b);
        if(find(a) == find(b)) x++;//环数量
        else f[f[a]] = f[b];//不成环
    }
    for(i=1; i<=n; i++){
        y += i == find(i);//连通块数量
    }
    printf("%d %d\n", x, y-x);
    return 0;
}

作者 crxis

发表回复