【板+并查集判断连通性】并查集判断连通性-白红宇

【板+并查集判断连通性】并查集判断连通性

阅读量：4307 次

发布时间：2019-06-06

本文共 1578 字，大约阅读时间需要 5 分钟。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 10 using namespace std;11 typedef long long ll;12 const int maxn=3002;13 int fa[maxn];14 int sum[maxn];15 int n,m;16 void init()17 {18 for(int i=1;i<=n;i++)19 {20 fa[i]=i;21 }22 }23 24 int find(int x)25 {26 return x==fa[x]?x:fa[x]=find(fa[x]);27 }28 int main()29 {30 while(~scanf("%d%d",&n,&m))31 {32 init();33 int u,v,w;34 memset(sum,0,sizeof(sum));35 int cnt=n-1;36 while(m--)37 {38 scanf("%d%d%d",&u,&v,&w);39 int fu=find(u);40 int fv=find(v);41 if(fu!=fv)42 {43 fa[fu]=fv;44 cnt--;45 }46 }47 if(cnt==0)48 {49 puts("yes");50 }51 else52 {53 puts("no");54 }55 }56 return 0;57 }

方法一

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;typedef long long ll;const int maxn=3002;int fa[maxn];int sum[maxn];int n,m;void init(){ for(int i=1;i<=n;i++) { fa[i]=i; }}int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]);}int main(){ while(~scanf("%d%d",&n,&m)) { init(); int u,v,w; memset(sum,0,sizeof(sum)); while(m--) { scanf("%d%d%d",&u,&v,&w); int fu=find(u); int fv=find(v); if(fu!=fv) { fa[fu]=fv; } } int cnt=0; for(int i=1;i<=n;i++) { if(fa[i]==i) cnt++; } if(cnt==1) { puts("yes"); } else { puts("no"); } } return 0;}