题目链接：https://pintia.cn/problem-sets/994805342720868352/exam/problems/994805344776077312

找段错误找了一个小时，纪念一下

你猜怎么着，我把M看成了N,N<300，我数组就开了1000，我甚至觉得很够了已经，结果人家M的范围压根没给，后来算算大概有5万。抛了个段错误我还一直以为是测试数据有问题，蠢死我了！！

这题我一开始按照dfs的套路去做了，但是最后一个节点超时了我靠：

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<cstring>
#include<unordered_map>
using namespace std;

#define inf 0x3f3f3f3f 

struct edge {
    string to;
    int next;
} g[50000];
int head[301], cnt;
string s, t;
unordered_map<string, int> M;
vector<vector<string> > res;
vector<string> path;
int vis[301], gender[301];

void dfs(string cur, int cur_step) {
    if (cur_step == 4) {
        // 找到
        res.push_back(path);
        return ;
    }
    if (cur_step == 1) {
        // 找和A同性的
        for (int i = head[M[cur]]; i; i = g[i].next) {
            string to = g[i].to;
            if (!vis[M[to]] && gender[M[to]] == gender[M[s]] && to != t) {
                vis[M[to]] = 1;
                path.push_back(to[0] == '-' ? to.substr(1, to.size() - 1) : to);
                dfs(to, cur_step + 1);
                path.pop_back();
                vis[M[to]] = 0;
            }
        }
    } else if (cur_step == 2){
        // 找和B同性的
        for (int i = head[M[cur]]; i; i = g[i].next) {
            string to = g[i].to;
            if (!vis[M[to]] && gender[M[to]] == gender[M[t]] && to != t) {
                vis[M[to]] = 1;
                path.push_back(to[0] == '-' ? to.substr(1, to.size() - 1) : to);
                dfs(to, cur_step + 1);
                path.pop_back();
                vis[M[to]] = 0;
            }
        }
    } else if (cur_step == 3) {
        // 找B
        for (int i = head[M[cur]]; i; i = g[i].next) {
            string to = g[i].to;
            if (!vis[M[to]] && to == t) {
                vis[M[to]] = 1;
                dfs(to, cur_step + 1);
                vis[M[to]] = 0;
            }
        }
    }
}
bool cmp(vector<string> &a, vector<string> &b) {
    return (a[0] < b[0]) || (a[0] == b[0] && a[1] < b[1]);
}
void output() {
    for (int i = 0; i < res.size(); i++) {
        cout << res[i][0] << " " << res[i][1] << endl;
    }
}
int n, m, k, num;
int main() {
    cin >> n>> m;

    for (int i = 0; i < m; i++) {
        string a, b;
        cin >> a >> b;
        if (M.find(a) == M.end()) {
            M[a] = ++num;
        }
        if (M.find(b) == M.end()) {
            M[b] = ++num;
        }
        g[++cnt] = edge{b, head[M[a]]};
        head[M[a]] = cnt;

        g[++cnt] = edge{a, head[M[b]]};
        head[M[b]] = cnt;

        gender[M[b]] = (b[0] != '-');
        gender[M[a]] = (a[0] != '-');
    }
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> s >> t;
        if (M.find(s) == M.end()) {
            cout << 0 << endl;
            continue;
        }
        memset(vis, 0, sizeof(vis));
        vis[M[s]] = 1;
        path.clear();
        res.clear();
        dfs(s, 1);
        sort(res.begin(), res.end(), cmp);
        printf("%d\n", res.size());
        output();
    }
    return 0;
}

没办法，两个半小时的苦苦挣扎之后再叫我再去优化代码，我可不干了。换个思路吧，看看柳神的代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
unordered_map<int, bool> arr;
struct node { // vector + 结构体就好了，妈的，我在搞什么二维的vector，多捞啊
    int a, b;
};
bool cmp(node x, node y) {
    return x.a != y.a ? x.a < y.a : x.b < y.b; // 三元表达式的写法，嘿嘿，学到了
}
int main() {
    int n, m, k;
    scanf("%d%d", &n, &m);
    vector<int> v[10000];
    for (int i = 0; i < m; i++) {
        string a, b;
        cin >> a >> b;
        if (a.length() == b.length()) { // 邻接表记录同性朋友，思路是真的清晰！
            v[abs(stoi(a))].push_back(abs(stoi(b))); // stoi() 这玩意为啥总是记不住？有前导零也不怕，照样盘它！
            v[abs(stoi(b))].push_back(abs(stoi(a)));
        }
        arr[abs(stoi(a)) * 10000 + abs(stoi(b))] = arr[abs(stoi(b)) * 10000 + abs(stoi(a))] = true; // 邻接矩阵一维化，有效地节省了空间，秀我一脸。。。
        // 连等是个技巧
    }
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        int c, d;
        cin >> c >> d;
        vector<node> ans;
        for (int j = 0; j < v[abs(c)].size(); j++) {
            for (int k = 0; k < v[abs(d)].size(); k++) {
                if (v[abs(c)][j] == abs(d) || abs(c) == v[abs(d)][k]) continue; // 朋友总不能直接是对象吧，也不能是自己吧，PASS PASS
                if (arr[v[abs(c)][j] * 10000 + v[abs(d)][k]] == true)
                    ans.push_back(node{v[abs(c)][j], v[abs(d)][k]});  // 我的朋友和你的朋友是不是朋友呢？两个for循环 woc 多么省力啊，我还搁那 dfs 半天写不清楚
            }
        }
        sort(ans.begin(), ans.end(), cmp); // 排完序就出来了，over！！
        printf("%d\n", int(ans.size()));
        for(int j = 0; j < ans.size(); j++)
            printf("%04d %04d\n", ans[j].a, ans[j].b); // 千万记得格式 %04d 上一题我就栽在这里了，耗了半个小时才发现
    }
    return 0;
}