AcWing 1632. 第一次接触
原题链接
中等
作者:
RainSure
,
2022-03-01 08:38:46
,
所有人可见
,
阅读 180
PAT的输入输出是最恶心的
#include<iostream>
#include<cstring>
#include<unordered_map>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 310;
#define x first
#define y second
typedef pair<string,string> PSS;
unordered_map<string, int> mp;
string num[maxn];
vector<int> boys, girls;
int n, m, idx;
int g[maxn][maxn];
int main()
{
cin >> n >> m;
while(m --)
{
string a, b; cin >> a >> b;
if(mp.count(a) == 0) mp[a] = ++ idx, num[idx] = a;
if(mp.count(b) == 0) mp[b] = ++ idx, num[idx] = b;
int x = mp[a], y = mp[b];
g[x][y] = g[y][x] = 1;
if(a[0] == '-') girls.push_back(x);
else boys.push_back(x);
if(b[0] == '-') girls.push_back(y);
else boys.push_back(y);
}
sort(boys.begin(), boys.end());
boys.erase(unique(boys.begin(), boys.end()), boys.end());
sort(girls.begin(), girls.end());
girls.erase(unique(girls.begin(), girls.end()), girls.end());
int k; cin >> k;
while(k --)
{
vector<PSS> res;
string a, b; cin >> a >> b;
int x = mp[a], y = mp[b];
auto p = boys, q = boys;
if(a[0] == '-') p = girls;
if(b[0] == '-') q = girls;
for(auto c : p){
for(auto d : q){
if(x != c && x != d && y != c && y != d && g[x][c] && g[c][d] && g[y][d]){
string p, q;
if(num[c].size() == 5) p = num[c].substr(1);
else p = num[c];
if(num[d].size() == 5) q = num[d].substr(1);
else q = num[d];
res.push_back({p, q});
}
}
}
cout << res.size() << endl;
sort(res.begin(), res.end());
for(auto item : res) {
cout << item.x << " " << item.y << endl;
}
}
return 0;
}