洛谷P8396题解

Ginger_he · 2022-06-12 16:39:52 · 题解

双倍经验：P8403 [CCC 2022 J4] Good Groups

题目描述

一个班级会被分成 g 个组，每个组有三个人，这种分组方式可能会违反两种规定：

1. 一些学生必须在同一小组

2. 一些学生必须不在同一小组

现在校长找到了你，问有多少条规定被违反了。

题解

我们用 unordered_map 把每个学生的名字映射成一个编号，然后在同一小组的用并查集合并，最后一条一条判断即可。

注意

• 因为 1\le g\le10^5，而每一行有三个学生的名字，所以最多有 3\times10^5 个学生，数组别开小了。

Code

#include<bits/stdc++.h>
using namespace std;
#define N 300005
int n,m,k,x,y,z,cnt,ans;
int f[N][2],g[N][2],p[N];
string s,t,u;
vector<int> v;
unordered_map<string,int> mp;
void build(string s)
{
    if(!mp[s])
    {
        mp[s]=++cnt;
        p[cnt]=cnt;
        v.push_back(cnt);
    }
}
int find(int x)
{
    if(x==p[x])
        return x;
    return p[x]=find(p[x]); 
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>s>>t;
        build(s),build(t);
        f[i][0]=mp[s],f[i][1]=mp[t];
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        cin>>s>>t;
        build(s),build(t);
        g[i][0]=mp[s],g[i][1]=mp[t];
    }
    scanf("%d",&k);
    for(int i=1;i<=k;i++)
    {
        cin>>s>>t>>u;
        build(s),build(t),build(u);
        x=find(mp[s]),y=find(mp[t]),z=find(mp[u]);
        p[y]=p[z]=x;
    }
    for(auto i:v)
        find(i);
    for(int i=1;i<=n;i++)
        ans+=(p[f[i][0]]!=p[f[i][1]]);
    for(int i=1;i<=m;i++)
        ans+=(p[g[i][0]]==p[g[i][1]]);
    printf("%d\n",ans);
    return 0;
}