牛客算法竞赛入门课第四节习题 Part1（并查集基础）

加边的无向图 （思维+并查集）

题意：

给你一个 n 个点，m 条边的无向图，求至少要在这个的基础上加多少条无向边使得任意两个点可达

思路：

给定的m条边不一定能够联通所有点，只需要计算出联通块个数-1即可。
因为3个区域只需要2条边就可以联通，所以答案是个数-1。
求联通块的话，可以用并查集或dfs
类似的题：传送门

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
///联通块个数-1
int root[maxn],n,m;
int Find(int x){
    if(x!=root[x]) root[x]=Find(root[x]);
    return root[x];
}
void Union(int x,int y){
    x=Find(x),y=Find(y);
    if(x!=y) root[y]=x;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) root[i]=i;///并查集初始化
    int a,b;
    while(m--){
        scanf("%d%d",&a,&b);
        Union(a,b);
    }
    int num=0;
    for(int i=1;i<=n;i++)
        if(root[i]==i) num++;
    printf("%d\n",num-1);
    return 0;
}

任意点（特殊联通+并查集）

题意：

平面上有若干个点，从每个点出发，你可以往东南西北任意方向走，直到碰到另一个点，然后才可以改变方向。 请问至少需要加多少个点，使得点对之间互相可以到达。

思路：

相当于是加边的无权图的加强版。不同的是两个点的联通条件是横坐标或纵坐标相同。

代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
#define I_int ll
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char F[200];
inline void out(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
    cout<<endl;
}

const int maxn=1100;
PII a[maxn];
int root[maxn];

int Find(int x){
    if(x!=root[x]) root[x]=Find(root[x]);
    return root[x];
}

void Union(int x,int y){
    x=Find(x),y=Find(y);
    if(x!=y) root[x]=y;
}

int main(){
    int n=read();
    for(int i=1;i<=n;i++) 
        root[i]=i;///并查集初始化
    for(int i=1;i<=n;i++){
        a[i].first=read();
        a[i].second=read();
    }
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            if(a[i].first==a[j].first||a[i].second==a[j].second)
                Union(i,j);
    int res=0;
    for(int i=1;i<=n;i++)
        if(root[i]==i) res++;
    out(res-1);
    return 0;
}

B-经商 （并查集+01背包）

题意：

给定关系网和每个人的消耗精力值和利益值，问在能力范围内最多能够获得的利益值是多少。

思路：

简单但又综合的题目。

首先因为他只能和能接触到的人交际，所以首先要根据并查集判断出有哪些人和他交际，即在一个联通块内。

然后就是一个背包问题了，跑一遍01背包即可。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
#define I_int ll
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char F[200];
inline void out(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
    cout<<endl;
}

const int maxn=100010;

int root[maxn];
int n,m,c;
int a[maxn],b[maxn];
int v[maxn],w[maxn];
int dp[maxn];

int Find(int x){
    if(x!=root[x]) root[x]=Find(root[x]);
    return root[x];
}

void Union(int x,int y){
    x=Find(x),y=Find(y);
    if(x!=y) root[x]=y;
}

int main(){
    int T=read();
    while(T--){
        n=read();m=read();c=read();
        for(int i=1;i<=n;i++) root[i]=i;
        for(int i=2;i<=n;i++) a[i]=read(),b[i]=read();
        while(m--){
            int x=read(),y=read();
            Union(x,y);
        }
        int Root=Find(1),tot=0;
        for(int i=2;i<=n;i++)
            if(Root==Find(i)) w[tot]=a[i],v[tot]=b[i],tot++;
        memset(dp,0,sizeof dp);
        for(int i=0;i<tot;i++)
            for(int j=c;j>=w[i];j--)
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        cout<<dp[c]<<endl;
    }

    return 0;
}