自动搬运

查看原文

来自洛谷，原作者为

	Ginger_he .

搬运于2025-08-24 22:38:43，当前版本为作者最后更新于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;
}