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;
}