当前位置：首页 > news >正文

并查集..

news 来源：原创 2024/9/18 8:37:47

Problem - 893C - Codeforces（求连通块内最小值）

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;const int N=1e5+10;
int p[N],s[N];int find(int x)
{if(p[x]!=x) p[x]=find(p[x]);return p[x];
}
void merge(int u,int v)
{u=find(u);v=find(v);if(s[u]>s[v]){p[u]=v;}else{p[v]=u;}
}
void solve()
{int n,m;cin>>n>>m;for(int i=1; i<=n;i ++) p[i]=i;for(int i=1; i<=n;i ++) cin>>s[i];for(int i=1, u,v; i<=m; i++){cin>>u>>v;merge(u,v);}LL ans=0;for(int i=1; i<=n; i++){if(find(i)==i) ans+=s[i];}cout<<ans<<'\n';
}int main()
{int T;
//	cin>>T;T=1;while(T--){solve();}return 0;
}

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;const int N=1e5+10;
int p[N],s[N];int find(int x)
{if(p[x]!=x) p[x]=find(p[x]);return p[x];
}
void merge(int u,int v)
{u=find(u);v=find(v);if(u!=v){p[v]=u;s[u]=min(s[u],s[v]);}
}
void solve()
{int n,m;cin>>n>>m;for(int i=1; i<=n;i ++) p[i]=i;for(int i=1; i<=n;i ++) cin>>s[i];for(int i=1, u,v; i<=m; i++){cin>>u>>v;merge(u,v);}LL ans=0;for(int i=1; i<=n; i++){if(find(i)==i) ans+=s[i];}cout<<ans<<'\n';
}int main()
{int T;
//	cin>>T;T=1;while(T--){solve();}return 0;
}

Problem - 977E - Codeforces（简单环）

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;const int N=2e5+10;
int p[N],d[N];
bool st[N];
int find(int x)
{if(p[x]!=x) p[x]=find(p[x]);return p[x];
}void solve()
{int n,m;cin>>n>>m;for(int i=1; i<=n;i ++) p[i]=i;for(int i=0, a,b;i<m; i++){cin>>a>>b;p[find(a)]=find(b);d[a]++, d[b]++;}for(int i=1; i<=n; i++){if(d[i]!=2) st[find(i)]=true;}int res=0;for(int i=1; i<=n; i++){if(find(i)==i && !st[find(i)]) res++;}cout<<res<<'\n';
}int main()
{int T;
//	cin>>T;T=1;while(T--){solve();}return 0;
}

Problem - 1167C - Codeforces（求连通块的大小）

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;const int N=5e5+10;
int p[N],d[N];
bool st[N];
int find(int x)
{if(p[x]!=x) p[x]=find(p[x]);return p[x];
}
void merge(int a,int b)
{int r1=find(a);int r2=find(b);p[r2]=r1;
} 
void solve()
{int n,m;cin>>n>>m;for(int i=1; i<=n; i++) p[i]=i;while(m--){int q;cin>>q;if(q==0) continue;int a;cin>>a;for(int i=1,b; i<q; i++){cin>>b;merge(a,b);}}vector<int> ans(n+1);for(int i=1; i<=n; i++){ans[find(i)]++;}for(int i=1; i<=n; i++){cout<<ans[find(i)]<<' ';}cout<<'\n';
}int main()
{int T;
//	cin>>T;T=1;while(T--){solve();}return 0;
}