P8403 [CCC2022 J4] Good Groups

题目背景

请注意：这道题是 CCO 2022 S2 Good Groups 的弱化版

管理备注：似乎没有弱化

题目描述

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

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

现在校长找到了你，问学生一共违反了多少个规定。

输入格式

第一行一个整数 x。紧接着 x 行，每行两个学生名字 name1​,name2​ ，表示这两个学生必须被分配到同一个小组。

接下来一个整数 y。紧接着 y 行，每行两个学生名字 name1​,name2​ ，表示这两个学生必须不在同一个小组。

接下来一个整数 g。紧接着 g 行，每行三个学生名字name1​,name2​,name3​，表示这三个学生现在被分在一个小组。

输出格式

输出一个整数，表示学生一共违反了多少个规定。

输入输出样例

输入 #1

1
ELODIE CHI
0
2
DWAYNE BEN ANJALI
CHI FRANCOIS ELODIE

输出 #1

0

输入 #2

3
A B
G L
J K
2
D F
D G
4
A C G
B D F
E H I
J K L

输出 #2

3

说明/提示

样例2解释：

1. A 和 B 必须在同一组，这一点违反了。
2. G 和 L 必须在同一组，这一点违反了。
3. J 和 K 必须在同一组，这一点没有违反。
4. D 和 F 必须不在同一组，这一点违反了。
5. D 和 G 必须不在同一组，这一点没有被违反。

以上 5 条共违反 3 条，所以输出 3。

对于 25% 的数据：1≤g≤50,1≤x≤50,y=0

对于另外 60% 的数据：1≤g≤50,1≤x≤50,1≤y≤50

对于 100% 的数据：1≤g≤10^5,1≤x≤10^5,1≤y≤10^5

代码

#include<iostream>
#include<map>
using namespace std;
struct must_in{//定义必须在一组的人的名字string name1,name2;
}m_i[100005];
struct must_not_in{定义必须不在一组的人的名字string name1,name2;
}m_n_i[100005];
struct now{//定义已经分好的组string name1,name2,name3;
}no[100005];
map<string,string>mp;//使用map映射函数
int main()
{int x,y,g;cin>>x;for(int i=1;i<=x;i++){cin>>m_i[i].name1>>m_i[i].name2;}cin>>y;for(int i=1;i<=y;i++){cin>>m_n_i[i].name1>>m_n_i[i].name2;}cin>>g;for(int i=1;i<=g;i++){cin>>no[i].name1>>no[i].name2>>no[i].name3;mp[no[i].name1]=no[i].name1;//对于每个分组，让第一个名字的父节点指向自己mp[no[i].name2]=no[i].name1;//对于每个分组，让第二个名字的父节点指向第一个名字mp[no[i].name3]=no[i].name1;//对于每个分组，让第三个名字的父节点指向第一个名字}int cnt=0;//统计违反规定的组的数量string xx,yy;for(int i=1;i<=x;i++){xx=mp[m_i[i].name1];//寻找第一个名字的父节点yy=mp[m_i[i].name2];//寻找第二个名字的父节点if(xx!=yy) cnt++;//判断是否违反规定}for(int i=1;i<=y;i++){xx=mp[m_n_i[i].name1];//寻找第一个名字的父节点yy=mp[m_n_i[i].name2];//寻找第二个名字的父节点if(xx==yy) cnt++;//判断是否违反规定}cout<<cnt;return 0;
}