首页 > > 程序设计 > C/C++ >

寒假集训第一天---并查集题解

2020-01-15 16:01:10来源：博客园阅读 ()

寒假集训第一天---并查集题解

CodeForces - 209C Trails and Glades

传送门

题目大意：n个点，m条边。从一号点出发，需要遍历所有有边相连的所有点最后要到一号点。(1 ≤ n ≤ 10⁶; 0 ≤ m ≤ 10⁶)

解法：跑出连通块个数和每个连通块所包含的度数为奇数的点，对于包含2个以上奇度顶点的连通块，先两两相连到只剩两个奇度顶点，然后所有连通块由奇度顶点出发连到另外一个块的奇度顶点，如果一个连通块没有奇度顶点，那就从任意一个偶度顶点出发，从同一偶度顶点回归。统计连通块用并查集

卡点：给的边可能没有连接1号顶点，需要从1号顶点出发和别的连通块相连，边数+1，但是如果一条边都没有，那结果就是0，因为没有其他点了.（看cf样例特判写过.....）

代??

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10 ;
int fa[maxn], cnt[maxn], vis[maxn], arr[maxn] ;
int fi(int x)
{
    return x == fa[x] ? x : fa[x] = fi(fa[x]) ;
}
int main(int argc, char const *argv[])
{
    int n , m ;
    scanf("%d %d",&n,&m) ;
    for(int i = 1 ; i <= n ; ++ i) fa[i] = i, cnt[i] = 0, vis[i] = 0, arr[i] = 0 ;
    for(int i = 1, a, b ; i <= m ; ++ i)
    {
        scanf("%d %d",&a,&b) ;
        cnt[a] ++ ;
        cnt[b] ++ ;
        vis[a] = 1 ;
        vis[b] = 1 ;
        int fx = fi(a), fy = fi(b) ;
        if(fx != fy) fa[fx] = fy ;
    }
    int ans = 0 , tot = 0 ;
    for(int i = 1 ; i <= n ; ++ i)
    {
        if(cnt[i] % 2 == 1)
        {
            arr[fi(i)] ++ ;
        }
    }
    int ff = 0 ;
    int cnt2 = 0 , cnt1 = 0;
    for(int i = 2 ; i <= n ; ++ i) if(vis[i] == 1) ff = 1 ;
    int cnt = 0 ;
    for(int i = 1 ; i <= n ; ++ i)
    {
        if(vis[i] && fa[i] == i && arr[i] >= 2)//有奇度顶点的连通块
        {
            tot = tot + (arr[i] - 2) / 2 ;
            ++ cnt2 ;//奇度顶点数
        }
        if(vis[i] && fa[i] == i) tot += 1, cnt ++ ;//顶点数
    }
    cnt1 = cnt - cnt2 ;
    //printf("%d %d %d\n",cnt1,cnt2,cnt) ;
    if(cnt == 1)
    {
        if(cnt1 == 1)
        {
            if(vis[1] == 0) printf("2\n") ;
            else printf("0\n") ;
        }
        else if(cnt2 == 1)
        {
            if(vis[1] == 0) tot ++ ;
            printf("%d\n",tot) ;
        }
    }
    else if(cnt == 0)
    {
        printf("0\n") ;
    }
    else if(cnt >= 2)
    {
        if(vis[1] == 0) ++ tot ;
        printf("%d\n",tot) ;
    }
    return 0;
}

View Code

CodeForces - 468B Two Sets

传送门

题目大意：第一行n,a,b，第二行n个数。问能否分成两个集合A B，对于集合A里面的数A_i，满足A-A_i也在A集合里，B同理。若可以分成两个集合输出YES，否则输出NO

解法：假设序列满足条件，那对每一个数而言，不在A，就在B，只需要设置n+1，n+2的两个集合保存不在B，不在A的数，合并，对于在A的点，就把A-A_i和A合并，如果Find(n+1) == Find(n+2)成立的话,说明不存在合理方案，反之序列合理

卡点：一开始的做法分成了四个集合，存A存B存!A存!B，结果在判断的时候写炸了

代??

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10 ;
int fa[maxn], arr[maxn], brr[maxn] ;
set<int> se ;
map<int,int> mp ;
int fd(int x)
{
    return x == fa[x] ? fa[x] : fa[x] = fd(fa[x]) ;
}
void un(int x , int y)
{
    int xx = fd(x) ;
    int yy = fd(y) ;
    if(xx != yy) fa[yy] = xx ;
}
int main(int argc, char const *argv[])
{
    int n, a, b ;
    se.clear() ;
    mp.clear() ;
    scanf("%d %d %d",&n,&a,&b) ;
    memset(brr,-1,sizeof brr) ;
    for(int i = 1 ; i <= n ; ++ i)
    {
        scanf("%d",&arr[i]) ;
        fa[i] = i ;
        se.insert(arr[i]) ;
        mp[arr[i]] = i ;
    }
    fa[n+1] = n+1 ; fa[n+2] = n+2 ;
    for(int i = 1 ; i <= n  ; ++ i)
    {
        if(se.count(a-arr[i])) un(i,mp[a-arr[i]]) ;
        else un(i,n+1) ;

        if(se.count(b-arr[i])) un(i,mp[b-arr[i]]) ;
        else un(i,n+2) ;
    }
    if(fd(n+1) == fd(n+2))
    {
        printf("NO\n") ;
        return 0 ;
    }
    printf("YES\n") ;
    for(int i = 1 ; i <= n ; ++ i)
    {
        printf("%d%c",(fd(i) == fd(n+1) ? 1 : 0)," \n"[i == n]) ;
    }
    return 0;
}

View Code

CodeForces - 722C Destroying Array

传送门

题目大意：对于一个序列，每次删除一个位置的数，每次的值等于删除这个数之后每个子串的各自权值和的最大值

解法：反向操作，删除变插入，用并查集维护即可

卡点：无

代??

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10 ;
#define ll long long
ll arr[maxn], val[maxn], val2[maxn] ;
int brr[maxn], fa[maxn], vis[maxn] ;
int fi(int x)
{
    return x == fa[x] ? fa[x] : fa[x] = fi(fa[x]) ;
}
int main(int argc, char const *argv[])
{
    int n ;
    scanf("%d",&n) ;
    memset(val,0,sizeof val) ;
    memset(vis,0,sizeof vis) ;
    memset(val2,0,sizeof val2) ;
    for(int i = 1 ; i <= n ; ++ i) scanf("%lld",&arr[i]), fa[i] = i ;
    for(int i = 1 ; i <= n ; ++ i) scanf("%d",&brr[n-i+1]) ;
    ll MAX = 0 ;
    for(int i = 1 ; i <= n ; ++ i)
    {
        val2[i] = MAX ;
        int pos = brr[i] ;
        vis[pos] = 1 ;
        int xx = fi(pos) ;
        int yy ;
        if(pos != 1)
        {
            if(vis[pos-1])
            {
                yy = fi(pos-1) ;
                val[pos] += val[yy] ;
                if(xx != yy) fa[yy] = xx ;
            }
        }
        if(pos != n)
        {
            if(vis[pos+1])
            {
                yy = fi(pos+1) ;
                val[pos] += val[fi(pos+1)] ;
                if(xx != yy) fa[yy] = xx ;
            }
        }
        val[pos] += arr[pos] ;
        MAX = max(MAX,val[pos]) ;
    }
    for(int i = n ; i >= 1 ; -- i) printf("%lld\n",val2[i]) ;
    return 0;
}

View Code

CodeForces - 1013D Chemical table

传送门

题目大意：二维平面中一个矩阵的三个顶点存在就可以默认矩阵另一个顶点存在，问给了P个点之后最少需要添加多少个点

解法：对于一张表，我如果有一行一列就可以填满，如果把这些点称为有效点，我需要n+m-1个有效点，所以从P中确定有多少个有效点即可。确定该点是否有效借助并查集即可

卡点：思维

代??

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10 ;
int fa[maxn] ;
int fi(int x)
{
    return x == fa[x] ? fa[x] : fa[x] = fi(fa[x]) ;
}
int main(int argc, char const *argv[])
{
    int n, m, q ;
    int ans = 0 ;
    scanf("%d %d %d",&n,&m,&q) ;
    ans = m + n - 1 ;
    for(int i = 0 ; i <= n+m+5+m ; ++ i) fa[i] = i ;
    for(int i = 1, x, y ; i <= q ; ++ i)
    {
        scanf("%d %d",&x,&y) ;
        y += m+n ;
        int fx = fi(x) ;
        int fy = fi(y) ;
        if(fx != fy)
        {
            fa[fy] = fx ;
            ans -- ;
        }
    }
    printf("%d\n",ans) ;
    return 0;
}

View Code

CodeForces - 1131D Chemical table

传送门

题目大意：给出n个点和m个点两两之间的n*m对关系，<,>,=，给出每个点合法的的最小权值，权值最小为1。权值大小关系即为两两之间关系。

解法：把相等的点用并查集缩成一个点，再跑拓扑排序

卡点：思维

代??

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e4 + 10 ;
const int maxn = 1e3 + 10 ;
#define pii pair<int,int>
char mp[maxn][maxn] ;
int fa[maxn*2] ;
int vis[maxn*2] ;
set<int> se ;
vector<int> ve[maxn*2] ;
int du[maxn*2] ;
int ans[maxn*2] ;
int Find(int x)
{
    return x == fa[x] ? fa[x] : fa[x] = Find(fa[x]) ;
}
void merge(int x, int y)
{
    int fx = Find(x), fy = Find(y) ;
    if(fx != fy)
    {
        fa[fx] = fy ;
    }
}
int main(int argc, char const *argv[])
{
    int n, m ;
    se.clear() ;
    memset(vis,0,sizeof vis) ;
    memset(ans,0,sizeof ans) ;
    scanf("%d %d",&n,&m) ;
    for(int i = 1 ; i <= m+n ; ++ i) fa[i] = i, du[i] = 0 ;
    for(int i = 1 ; i <= n ; ++ i)
    {
        scanf("%s",mp[i]+1) ;
        for(int j = 1 ; j <= m ; ++ j) if(mp[i][j] == '=') merge(i,j+n) ;
    }

    for(int i = 1 ; i <= n ; ++ i)
    {
        for(int j = 1 ; j <= m ; ++ j)
        {
            if(mp[i][j] == '=') merge(i,j+n) ;
        }
    }
    for(int i = 1 ; i <= n ; ++ i)
    {
        for(int j = 1 ; j <= m ; ++ j)
        {
            if(mp[i][j] == '>') ve[Find(j+n)].push_back(Find(i)), du[Find(i)] ++ ;
            else if(mp[i][j] == '<') ve[Find(i)].push_back(Find(j+n)) , du[Find(j+n)] ++ ;
        }
    }
    stack<int> st ;
    for(int i = 1 ; i <= n + m ; ++ i)
    {
        if(du[Find(i)] == 0 && vis[Find(i)] == 0)
        {
            vis[Find(i)] = 1 ;
            st.push(Find(i)) ;
            ans[Find(i)] = 1 ;
        }
    }
    while(!st.empty())
    {
        int u = st.top() ;
        st.pop() ;
        for(int i = 0 ; i < ve[u].size() ; ++ i)
        {
            int v = ve[u][i] ;
            du[Find(v)] -- ;
            if(du[Find(v)] == 0  && vis[Find(v)] == 0)
            {
                st.push(Find(v)) ;
                vis[Find(v)] = 1 ;
                ans[Find(v)] = ans[Find(u)] + 1 ;
            }
        }
    }
    for(int i = 1 ; i <= n + m ; ++ i)
    {
        if(vis[Find(i)] == 0)
        {
            printf("NO\n") ;
            return 0 ;
        }
    }
    printf("YES\n") ;
    for(int i = 1 ; i <= n ; ++ i) printf("%d%c",ans[Find(i)]," \n"[i == n]) ;
    for(int i = n + 1 ; i <= n + m ; ++ i) printf("%d%c",ans[Find(i)]," \n"[i == n]) ;
    return 0;
}

View Code

CodeForces - 1166E Chemical table

传送门

题解

代??

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 10 ;
int arr[55][maxn] ;
int vis[550][maxn] ;
int main(int argc, char const *argv[])
{
    int m, n ;
    scanf("%d %d",&m,&n) ;
    memset(vis,0,sizeof vis) ;
    for(int i = 1, cnt ; i <= m ; ++ i)
    {
        scanf("%d",&cnt) ;
        arr[i][0] = cnt ;
        for(int j = 1 ; j <= cnt ; ++ j) scanf("%d",&arr[i][j]), vis[i][arr[i][j]] = 1 ;
    }
    int flag = 0 ;
    for(int i = 1 ; i <= m ; ++ i)
    {
        for(int j = 1 ; j <= m ; ++ j)
        {
            flag = 0 ;
            for(int k = 1 ; k <= n ; ++ k)
            {
                if(vis[i][k] && vis[j][k]) flag = 1 ;
            }
            if(flag == 0)
            {
                printf("impossible\n") ;
                return 0 ;
            }
        }
    }
    printf("possible\n") ;
    return 0;
}

View Code

HDU - 3047 Zjnu Stadium

传送门

题目大意：给出m对关系，意味着Yi离Xi有多远，围城300个点的圈就坐，问有多少对关系是不合法的

解法：带权并查集模板

卡点：模板，不用取模，因为每个点后右无限座位

代??

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 10 ;
const int mod = 300 ;
int ans = 0 ;
int fa[maxn], sum[maxn] ;
int fi(int x)
{
    if(fa[x] != x)
    {
        int root = fa[x] ;
        fa[x] = fi(fa[x]) ;
        sum[x] = sum[root] + sum[x] ;
    }
    return fa[x] ;
}
int main(int argc, char const *argv[])
{
    int n, m ;

    while(scanf("%d %d",&n,&m) != EOF)
    {
        ans = 0 ;
        for(int i = 1 ; i <= n ; ++ i) fa[i] = i, sum[i] = 0 ;
        for(int i = 1, x, y, s ; i <= m ; ++ i)
        {
            scanf("%d %d %d",&x,&y,&s) ;
            int fx = fi(x), fy = fi(y) ;
            if(fx == fy)
            {
                if(s != sum[x] - sum[y]) ans ++ ;
            }
            else
            {
                fa[fx] = fy ;
                sum[fx] = s - sum[x] + sum[y] ;
            }
        }
        printf("%d\n",ans) ;
    }

    return 0;
}