大数据下秩优化节约50%时间
#include<bits/stdc++.h> using namespace std; typedef struct{ int parent; int rank; }NODE;NODE arr[10010]={0,0}; int find(int key) {//路径压缩 if(arr[key].parent!=key) arr[key].parent=find(arr[key].parent); return arr[key].parent; } int main() { int n,m;cin>>n>>m; for(int i=0;i<10010;i++) { arr[i].parent=i; arr[i].rank=0; } while(m--) { int z;cin>>z; if(z==1) { int a,b;cin>>a>>b; int fa=find(a),fb=find(b);//秩优化 if(arr[fa].rank>arr[fb].rank) { arr[fb].parent=arr[fa].parent; arr[fa].rank++; } else { arr[fa].parent=arr[fb].parent; arr[fb].rank++; } } if(z==2) { int a,b;cin>>a>>b; if(arr[find(a)].parent==arr[find(b)].parent) printf("Y\n"); else printf("N\n"); } } } #include<bits/stdc++.h> using names
阅读背景：
并查集-路径优化+秩优化
来源：互联网
分享到：
