3 条题解

  • 2
    @ 2023-6-22 0:51:43
    #include<bits/stdc++.h>
    using namespace std;
    int fa[30001],front[30001],num[30001],x,y,i,j,n,T,ans;    
    
                                             
    char ins;
    int find(int n){                                        
        if(fa[n]==n)return fa[n];
        int fn=find(fa[n]);                                   
        front[n]+=front[fa[n]];    
                                        
        return fa[n]=fn;
    }
    int main(){
        cin>>T;
        for(i=1;i<=30000;++i){                                 
            fa[i]=i;
            front[i]=0;
            num[i]=1;
        }
        while(T--){
            cin>>ins>>x>>y;
            int fx=find(x);                                    
            int fy=find(y);                                    
            if(ins=='M'){
                front[fx]+=num[fy];        
                fa[fx]=fy;                                   
                num[fy]+=num[fx];                            
                num[fx]=0;                        
            }
            if(ins=='C'){
                if(fx!=fy)cout<<"-1"<<endl;            
                else cout<<abs(front[x]-front[y])-1<<endl;    
            }
        }
        return 0;
    }
    
    • 1
      @ 2023-6-21 8:58:13
      #include <cstdio>
      #include <cctype>
      #include <cmath>
      
      const int M=30000;
      
      int n;
      int f[M+10],dis[M+10];
      int size[M+10];
      
      inline int read(void)
      {
          int x=0; char c=getchar();
          for (;!isdigit(c);c=getchar());
          for (;isdigit(c);c=getchar()) x=x*10+c-'0';
          return x;
      }
      
      int findf(int i)
      {
          if (f[i]==i) return i;
          int pre=f[i],anc=findf(f[i]);
          f[i]=anc,dis[i]+=dis[pre];
          return anc;
      }
      
      int main(void)
      {
          n=read();
          for (int i=1;i<=M;i++) f[i]=i,size[i]=1;
      
          char c; int x,y; int fx,fy;
          for (int i=1;i<=n;i++)
          {
              scanf("\n"); c=getchar(); x=read(),y=read();
              fx=findf(x),fy=findf(y);
              if (c=='M')
              {
                  f[fx]=fy;
                  dis[fx]=size[fy];
                  size[fy]+=size[fx];
              }
              else printf("%d\n",fx!=fy?-1:dis[x]<dis[y]?dis[y]-dis[x]-1:dis[x]-dis[y]-1);
          }
      
          return 0;
      }
      
      • 0
        @ 2023-6-30 11:18:38

        image image

        #include <bits/stdc++.h>
        using namespace std;
        const int n=30000;
        int m,k,s,t,fa[n+5],size[n+5],d[n+5],ss,tt;
        int getfa(int x){
            if (fa[x]==x) return x;//当前是根节点,直接返回x 
            int p=getfa(fa[x]);//p 是根节点 
            d[x]+=d[fa[x]];//此时的fa[x]已经指向了p,d[fa[x]]中保存的是fa[x]到p的距离
        	//d[x]+=d[fa[x]]就可以得到x到p的距离了 
            fa[x]=p;//更新fa[x] 
            return p;
        }
        int main() {
            cin>>m;
            for (int i=1;i<=n;++i){
                fa[i]=i;
                size[i]=1;
            }
            char c;
            for (int i=1;i<=m;++i){
                c=getchar();
                while (c!='C' && c!='M')
                    c=getchar();
                cin>>x>>y;
                s=getfa(x);
                t=getfa(y);
                if (c=='C'){
                    if (s!=t) cout<<-1<<endl;//不在同一列 
                    else cout<<abs(d[x]-d[y])-1<<endl;//在同一列输出距离差 
                }
                else {
                    fa[s]=t;
                    d[s]=size[t];//整体排在以t为根的集合后面,首元素s距离t有size[t]的距离 
                    size[t]+=size[s];
                }
            }
        }
        
        
        
        
        • 1

        信息

        ID
        217
        时间
        1000ms
        内存
        128MiB
        难度
        4
        标签
        递交数
        80
        已通过
        40
        上传者