1139 First Contact(unique函数，string.substr()函数)

PTA | 程序设计类实验辅助教学平台

用map套个set来实现邻接表（排序都免了）

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
string a,b;
map<string,set<string>>mp;
int main()
{cin.tie(0);cin >> n >> m;for(int i = 0; i < m; i ++){cin >> a >> b;mp[a].insert(b),mp[b].insert(a);}cin >> k;while(k --){cin >> a >> b;vector<pair<int,int>>ans;for(auto c : mp[a]){if(c.size() != a.size() || c == b) continue;//不是同性或者朋友bfor(auto d : mp[b]){if(d.size() !=  b.size() || d == a) continue;//不是同性或者朋友aif(mp[c].count(d)) ans.push_back({abs(stoi(c)),abs(stoi(d))});}}sort(ans.begin(),ans.end());printf("%d\n",ans.size());for(auto it : ans) printf("%04d %04d\n",it.first,it.second);}return 0;
}

常规做法： 

#include<bits/stdc++.h>
using namespace std;
const int N=310;
int n,m;
unordered_map<string,int>mp;
string num[N];
int id;
bool g[N][N];
vector<int>boys,girls;
int main()
{scanf("%d %d",&n,&m);while(m--){string a,b,x,y;cin>>a>>b;x=a,y=b;if(x[0]=='-')x=x.substr(1);if(y[0]=='-')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;int px=mp[x],py=mp[y];g[px][py]=g[py][px]=true;if(a[0]=='-')girls.push_back(px);elseboys.push_back(px);if(b[0]=='-')girls.push_back(py);elseboys.push_back(py);}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;scanf("%d",&k);while(k--){vector<pair<string,string>>res;string x,y;cin>>x>>y;vector<int>p=boys,q=boys;if(x[0]=='-')p=girls,x=x.substr(1);if(y[0]=='-')q=girls,y=y.substr(1);int a=mp[x],b=mp[y];for(int c:p){for(int d:q){if (c != a && c != b && d != a && d != b && g[a][c] && g[c][d] && g[d][b])res.push_back({num[c],num[d]});}}sort(res.begin(),res.end());printf("%d\n",res.size());for(auto p:res)cout<<p.first<<" "<<p.second<<endl;}return 0;
}