2023年9月1日

今天还总结了个STL。

ACWING5179 分组

题目理解

就是利用了哈希，我们可以使用unorder_map来快速实现。我们用pair来存每一对的情况，a代表想在一起的同学，b代表不想在一起的同学。随后用一个哈希表，来代表分组的情况。
然后我们就看想在一起的他们的分组在不在一起。不想在一起的是否分到了一起就可以了。

代码实现

#include<iostream>
#include<unordered_map>
#include<vector>
#include<cstring>
using namespace std;

const int N = 1e5 + 10;

pair<string, string> a[N], b[N];

unordered_map<string, int> p;

int main()
{
    int x, y;

    cin >> x;

    for(int i = 0; i < x; i++)
        cin >> a[i].first >> a[i].second;

    cin >> y;
    for(int i = 0 ; i < y; i++)
        cin >> b[i].first >> b[i].second;

    int n;
    cin >> n;

    int cnt = 0;

    for(int i = 1; i <= n; i++)
    {
        string n1, n2, n3;
        cin >> n1 >> n2 >> n3;

        p[n1] = p[n2] = p[n3] = i;
    }


    for(int i = 0 ; i < x; i++)
        if(p[a[i].first] != p[a[i].second])
            cnt++;

    for(int i = 0 ; i < y; i++)
        if(p[b[i].first] == p[b[i].second])
            cnt++;

    cout << cnt;

    return 0;
}