并查集例题
并查集的特别之处在于它能把几个不同的节点连接起来作为一个整体,所以可以用并查集解决的题一定是需要把节点连接成一个整体的
1:
该题就可以把攻击之前的敌国城市看做一个整体,判断攻击后还能不能成为一个整体
#include<bits/stdc++.h>
using namespace std;
int p[20000];
int visit[20000];
int l[20000];//边的起始点
int r[20000];//边的终止点
int n,m;
void init(){
for(int i=1;i<=n;i++){
p[i]=i;
}
}
int find(int x){
if(x==p[x]) return x;
return p[x]=find(p[x]);
}
void join(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy){
p[fx]=fy;
}
}
bool judge(){
for(int i=1;i<=n;i++){
if(p[i]!=i)
return false;
}
return true;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
l[i]=a;
r[i]=b;
}
int k;
cin>>k;
while(k--){
memset(visit,0,sizeof(visit));
init();//重新初始化;
int a;
cin>>a;
for(int i=1;i<=a;i++){
int b;
cin>>b;
visit[b]=1;
}
for(int j=1;j<=m;j++){
if(visit[l[j]]||visit[r[j]]) continue;
join(l[j],r[j]);
}
if(!judge()) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
}
就可以看做失去某城市前的该国城市分为len1个整体,失去该城市后该国的城市分为len2个整体,然后通过判断len2-len1来确定攻击该城市是否改变其他城市之间的连通性
#include<bits/stdc++.h>
using namespace std;
int p[1000];
int visit[1000];
int n,m;
struct Node{
int from;
int to;
};
Node node[10000];
void init(){
for(int i=0;i<n;i++){
p[i]=i;
}
}
int find(int x){
if(x==p[x]) return x;
return x=find(p[x]);
}
void join(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy){
p[fx]=fy;
}
}
int main(){
cin>>n>>m;
init();
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
node[i].from=a;
node[i].to=b;
join(a,b);
}
int num=0,num2=0;
for(int i=0;i<n;i++){
if(p[i]==i) num++;
}
int k;
cin>>k;
while(k--){
int a;
int num2=0;
cin>>a;
init();
visit[a]=1;
for(int i=0;i<m;i++){
if(visit[node[i].from]==1||visit[node[i].to]==1) continue;
join(node[i].from,node[i].to);
}
for(int i=0;i<n;i++){
if(p[i]==i){
num2++;
}
}
if(num==num2||num==num2-1){
cout<<"City "<<a<<" is lost."<<endl;
}
else{
cout<<"Red Alert: "<<"City "<<a<<" is lost!"<<endl;
}
num=num2;
}
int cnt=0;
for(int i=0;i<n;i++){
if(visit[i]==1) cnt++;
}
if(cnt==n) cout<<"Game Over."<<endl;
}
这个就很符合并查集的特征,就是判断有多少个圈子
#include<bits/stdc++.h>
using namespace std;
int p[20000];
int n;
set<int>s;
set<int>s1;
void init(){
for(int i=1;i<=10000;i++){
p[i]=i;
}
}
int find(int x){
if(x==p[x]) return x;
return p[x]=find(p[x]);
}
void join(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy){
p[fx]=fy;
}
}
int main(){
init();
cin>>n;
for(int i=1;i<=n;i++){
int k,b;
cin>>k;
cin>>b;
s.insert(b);
for(int i=2;i<=k;i++){
int a;
cin>>a;
s.insert(a);
join(a,b);
}
}
int sum1;
for(int i=1;i<=s.size();i++){
s1.insert(find(p[i]));
}
cout<<s.size()<<" ";
cout<<s1.size()<<endl;
int cnt=0;
cin>>sum1;
for(int i=1;i<=sum1;i++){
int a,b;
cin>>a>>b;
if(find(a)==find(b)){
cout<<"Y"<<endl;
}
else{
cout<<"N"<<endl;
}
}
}
这个就可以将有朋友关系的看作一个整体(可以是朋友的朋友)
然后判断即可
#include<bits/stdc++.h>
using namespace std;
int maps[200][200];
int p[200];
int find(int x){
if(x==p[x]) return x;
return x=find(p[x]);
}
void join (int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy){
p[fx]=fy;
}
}
int main(){
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
p[i]=i;
}
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
if(c==1){
join(a,b);
}
else {
maps[a][b]=1;
maps[b][a]=1;
}
}
for(int i=1;i<=k;i++){
int a,b;
cin>>a>>b;
int x1=find(a);
int x2=find(b);
if(x1==x2&&maps[a][b]==0){
cout<<"No problem"<<endl;
}
if(x1!=x2&&maps[a][b]==0){
cout<<"OK"<<endl;
}
if(x1!=x2&&maps[a][b]==1){
cout<<"No way"<<endl;
}
if(x1==x2&&maps[a][b]){
cout<<"OK but..."<<endl;
}
}
}
这个也是把一个家庭看作一个整体,然后把所有资产算在一个人身上,再求平均
#include<bits/stdc++.h>
using namespace std;
struct node{
int id=1e9,peoplenum=0;
double housesum=0;
double housearea=0;
};
int visit[20000];//记录出现过的节点
int vis[200000];//记录家庭有没有出现过
node ans[20000];
node ans1[20000];
int p[20000];
int num[20000];//记录房产数量
int area[20000];//记录房产面积
int find(int x){
if(x==p[x]) return x;
return p[x]=find(p[x]);
}
void join(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy){
p[fx]=fy;
}
}
bool cmp(node x , node y){
if(fabs(x.housearea - y.housearea) < 1e-10){ //double类型比较大小一定要设置精确度
return x.id< y.id;
}
else{
return x.housearea > y.housearea;
}
}
int main(){
int n;
cin>>n;
for(int i=0;i<=10000;i++){//编号最大9999
p[i]=i;
}
for(int i = 0; i < n; ++i){
int index , f , m , k , children;
cin >> index >> f >> m >> k;
visit[index] = 1;
if(f != -1){
visit[f] = 1;
join(index , f);
}
if(m != -1){
visit[m] = 1;
join(index , m);
}
for(int j = 0; j < k; ++j){
cin >> children;
visit[children] = 1;
join(index , children);
}
cin >> num[index] >> area[index];
}
for(int i=0;i<=9999;i++){
if(visit[i]){
p[i]=find(i);//将所有人的祖先设为父亲,便于以家庭为单位计算
}
}
vector <int > g;
for(int i = 0; i <= 9999; ++i){
if(visit[i] == 1){
if(!vis[p[i]]){//第一次统计这个家庭则家庭数加一
vis[p[i]] = 1;
g.push_back(p[i]); // 把这个家庭的号码记下
}
ans[p[i]].housesum += num[i];
ans[p[i]].housearea += area[i];
ans[p[i]].id= min(ans[p[i]].id, i);
ans[p[i]].peoplenum++;
}
}
cout<<g.size()<<endl;
for(int i=0;i<g.size();i++){
ans[g[i]].housesum/=ans[g[i]].peoplenum;
ans[g[i]].housearea/=ans[g[i]].peoplenum;
ans1[i]=ans[g[i]];
}
sort(ans1,ans1+g.size(),cmp);
for(int i=0;i<g.size();i++){
printf("%04d %d %.3lf %.3lf\n",ans1[i].id,ans1[i].peoplenum,ans1[i].housesum,ans1[i].housearea);
}
}
这道第十一届蓝桥杯省赛的题也可以用并查集解决
主要算法是dfs,这里并查集主要是检查亮的地方有没有相连
即查看有多少个圈
代码:
#include<bits/stdc++.h>
using namespace std;
int ans=0;
int maps[10][10];
int fa[10];
int vis[10];
int find(int i){
if(fa[i]==i) return i;
return fa[i]=find(fa[i]);
}
void dfs(int k){
if(k>7){
for(int i=1;i<=7;i++){
fa[i]=i;
}
for(int i=1;i<=7;i++){
for(int j=1;j<=7;j++){
if(maps[i][j]&&vis[i]&&vis[j]){
int fx=find(i);
int fy=find(j);
if(fx!=fy){
fa[fx]=fy;
}
}
}
}
int cnt=0;
for(int i=1;i<=7;i++){
if(fa[i]==i&&vis[i]){
cnt++;
}
}
if(cnt==1) ans++;
return;
}
vis[k]=1;
dfs(k+1);
vis[k]=0;
dfs(k+1);
cout<<k<<endl;
}
int main(){
maps[1][2]=maps[2][1]=1;maps[1][6]=maps[6][1]=1; //连通的存图
maps[6][7]=maps[7][6]=1;maps[6][5]=maps[5][6]=1;
maps[2][7]=maps[7][2]=1;maps[2][3]=maps[3][2]=1;
maps[5][7]=maps[7][5]=1;maps[5][4]=maps[4][5]=1;
maps[3][7]=maps[7][3]=1;maps[4][3]=maps[3][4]=1;
dfs(1);
cout<<ans;
}
版权声明：本文为cjmdyl原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。