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;//不是同性或者朋友b
            for(auto d : mp[b])
            {
                if(d.size() !=  b.size() || d == a) continue;//不是同性或者朋友a
                if(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);
        else
            boys.push_back(px);
        if(b[0]=='-')girls.push_back(py);
        else
            boys.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;
}