树结构练习——判断给定森林中有多少棵树-并查集

#include <stdio.h> #include <stdlib.h> #include <string.h> int vis[100002]; int find(int x) { int f=x,i; while(vis[f] != f) { f=vis[f]; } while(x != vis[x]) { i=vis[x]; vis[x]=f; x=i; } return(x); } void merg(int x,int y) { int fx=find(x); int fy=find(y); if(fx != fy) vis[fx]=fy; } int main() { int i,n,m,a,b; while(~scanf("%d%d",&n,&m)) { int ans=0; for(i=0;i<=n;i++)//先对每个二叉树节点标号 vis[i]=i; for(i=0;i<m;i++) { scanf("%d%d",&a,&b);//并查集连接成树 merg(a,b); } for(i=1;i<=n;i++) { if(vis[i] == i) ans++;//遍历节点依然等于自己本身的就是一棵独立二叉树 } printf("%d\n",ans); } return 0; }