Pat class a 1139 first contact

Original link

Different from today , The way boys and girls express love in their early years is quite subtle .

Be a boy A In love with a girl B When , He usually doesn't contact her directly .

In its place , He might find another boy C（ His good friend ） Go and ask the girl D（ She is B and C Friend, ） Will the girl B Make an appointment .

This is really trouble, isn't it ？

Girls can do similar things .

In a given friendship network , Please help some boys and girls list all the friends who may help them make the first contact .

Input format
The first line contains two integers N and M, It means the total number of people and the number of friendly relations .

Next M That's ok , Each line gives a pair of friends .

Everyone uses one 4 Bit number representation , To distinguish between genders , We put a minus sign in front of the girl's number .

The next line contains an integer K, Indicates the number of queries .

Next K That's ok , Each line contains a pair of secret relationships , Suppose the first person is secretly in love with the second person .

Output format
For each group ask , The first line outputs an integer , Indicates the number of different pairs of friends who can be found to help with the matchmaking .

then , Output the number of a pair of helpful friends on each line .

If A and B Of different genders , Then output and first A Friends of the same sex , Re output and B Friends of the same sex .

If A and B The same gender , Then two friends must be the same sex as them .

Make sure everyone has only one sex .

A group of questions , Friend pairs are sorted by the number of the first friend from small to large , When the first friend has the same number , Sort by the number of the second friend from small to large .

Data range
1<N≤300,
1≤M≤15000,
1≤K≤100
sample input ：
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
sample output ：
4
1002 2004
1003 2002
1003 2003
1004 2002
4
2001 1002
2001 1003
2002 1003
2002 1004
0
1
2003 2001
0

My solution :

#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;
}

Harvest ：

unique() Used to eliminate adjacent duplicate elements , The elimination here actually puts the repeating elements at the end , And return the index after the move

And erase Function combination , Can eliminate duplicate elements in the container