PAT甲级 1139 第一次接触

原题链接

与如今不同，早年男孩和女孩表达爱情的方式相当微妙。

当男孩 A 暗恋着女孩 B 的时候，他通常不会直接与她联系。

取而代之的是，他可能会去找另一个男孩 C（他的好朋友）去拜托女孩 D（她是 B 和 C 的朋友）将女孩 B 约出来。

这实在是麻烦不是吗？

女孩也会做类似的事情。

在给定的友谊关系网络中，请你帮助一些男孩和女孩列出所有可能会帮助他们进行第一次联系的朋友。

输入格式
第一行包含两个整数 N 和 M，分别表示总人数以及友好关系的数量。

接下来 M 行，每行给出一对朋友关系。

每个人都用一个 4 位数字表示，为了区分性别，我们在女生的编号前加了负号。

再一行包含一个整数 K，表示询问数量。

接下来 K 行，每行包含一对暗恋关系，假设第一个人暗恋着第二个人。

输出格式
对于每组询问，第一行输出一个整数，表示可以找到的帮忙牵线的不同朋友对的数量。

然后，在每行输出一对帮忙的朋友的编号。

如果 A 和 B 的性别不同，则先输出与 A 性别相同的朋友，再输出与 B 性别相同的朋友。

如果 A 和 B 的性别相同，则两个朋友的性别必须也和他们相同。

保证每个人只有一种性别。

一组询问内，朋友对按第一个朋友的编号从小到大进行排序，第一个朋友的编号相同时，按第二个朋友的编号从小到大进行排序。

数据范围
1<N≤300,
1≤M≤15000,
1≤K≤100
输入样例：
10 18
-2001 1001
-2002 -2001
1004 1001
-2004 -2001
-2003 1005
1005 -2001
1001 -2003
1002 1001
1002 -2004
-2004 1001
1003 -2002
-2003 1003
1004 -2002
-2001 -2003
1001 1003
1003 -2001
1002 -2001
-2002 -2003
5
1001 -2001
-2003 1001
1005 -2001
-2002 -2004
1111 -2003
输出样例：
4
1002 2004
1003 2002
1003 2003
1004 2002
4
2001 1002
2001 1003
2002 1003
2002 1004
0
1
2003 2001
0

我的解法:

#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int n, m;
int id;
bool g[N][N];
string num[N];
unordered_map <string, int> mp;
vector<int> girls, boys;
int main(){
    cin >> n >> m;
    char as[N], bs[N];
    while(m --){
        scanf("%s %s", as, bs);
        string a = as, b = bs;
        string x = a, y = b;
        if(x.size() == 5) x = x.substr(1);
        if(y.size() == 5) y = y.substr(1);
        if(mp.count(x) == 0) mp[x] = ++ id, num[id] = x;
        if(mp.count(y) == 0) mp[y] = ++ id, num[id] = y;
        
        g[mp[x]][mp[y]] = g[mp[y]][mp[x]] = true;
        
        if(a.size() == 5) girls.push_back(mp[x]);
        else boys.push_back(mp[x]);
        if(b.size() == 5) girls.push_back(mp[y]);
        else boys.push_back(mp[y]);
        
    }
    sort(girls.begin(), girls.end());
    girls.erase(unique(girls.begin(), girls.end()), girls.end());
    sort(boys.begin(), boys.end());
    boys.erase(unique(boys.begin(), boys.end()), boys.end());
    
    int k;
    cin >> k;
    while(k -- ){
        scanf("%s %s", as, bs);
        string x = as, y = bs;
        vector<pair<string, string>> res;
        
        vector<int> p = boys, q = boys;
        if(x.size() == 5) p = girls, x = x.substr(1);
        if(y.size() == 5) q = girls, y = y.substr(1);
        
        int a = mp[x], b = mp[y];
        for(auto c : p){
            for(auto d : q){
                if(a != c && b != d && c != b && d != a && g[a][c] && g[c][d] && g[d][b]){
                    res.push_back({num[c], num[d]});
                }
            }
        }
        sort(res.begin(), res.end());
        cout << res.size() << endl;
        for(int i = 0; i < res.size(); i ++ ){
            printf("%s %s\n", res[i].first.c_str(), res[i].second.c_str());
        }
    }
    return 0;
}

收获：

unique()用于消除相邻重复元素，这里的消除其实是把重复元素放到了最后，并且返回移动后的索引

与erase函数结合，可以消除容器中的重复元素