关于算法-数据结构:PAT甲级1139-First-Contact

题目粗心：

一张人际关系网络图，而后给出一对情侣 A 和 B(正数代表女生，负数代表男生)，要求找到 A 的敌人 (不是 B, 和 A 性别雷同)C,B 的敌人 (不是 A, 和 B 的性别雷同)D, 如果 C 和 D 是敌人那么输入 C 和 D 的编号 (输入的编号均为负数)，并且依照 C 的非递加排列，如果雷同，则依照 D 的升序排列。

算法思路：

对于每个人的编号保留其符号进行输出，应用 string 类型变量接管，这样，判断性别是否雷同直接判断两个字符串长度是否一样就行，并且为了简化搜寻，咱们用邻接表 Adj 只保留每一个人的同性敌人，而后再应用邻接矩阵保留所有的敌人关系，其行为男生，列为女生，这样就能够将女生转化为负数来进行保留，又因为题目的特殊性，从 A 到 B 的门路肯定得是一个长度为 4 的门路，那么就间接遍历每一个 A 的同性敌人和 B 的同性敌人，判断这两人是否是敌人就好。如果是就阐明找到了 C 和 D，并将其增加进 result 中，在遍历完结后，对 result 依照规定排序输入即可.

留神点：

• 1、此题没有必要应用 DFS，第一个起因是男生编号为 0000，女生编号为 -0000 的状况不是很好解决，第二是最初一个测试点会运行超时。
• 2、这里应用邻接表只保留同性敌人能够大大降低工夫复杂度。
• 3、对于 A 的敌人不能是 B，对于 B 的敌人不能是 A，这里是针对 A 和 B 是同性敌人的非凡解决，避免门路长度为 2.

提交后果：

AC 代码：

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<string>
#include<cmath>
#include<iostream>

using namespace std;

struct Pair{
    int first,second;
    Pair(int f,int s){
        first = f;
        second = s;
    }
};

vector<int> Adj[10000];// 邻接表 , 保留每一个人的同性敌人 
int G[10000][10000];// 邻接矩阵，用来判断任意 2 人是否是敌人 

bool cmp(const Pair &a,const Pair &b){return a.first!=b.first?a.first<b.first:a.second<b.second;}

int main(){
    int N,M;
    scanf("%d %d",&N,&M);
    string a,b;
    for(int i=0;i<M;++i){
        cin>>a>>b;
        int A = abs(stoi(a));
        int B = abs(stoi(b));
        if(a.size()==b.size()){
            // a 和 b 是同性敌人 
            Adj[A].push_back(B);
            Adj[B].push_back(A);
        }
        G[A][B] = G[B][A] = 1;
    }
    int K;
    scanf("%d",&K);
    for(int i=0;i<K;++i){
        vector<Pair> result;
        cin>>a>>b;
        int A = abs(stoi(a));
        int B = abs(stoi(b));
        // 遍历 A 的同性敌人 
        for(auto &friendA:Adj[A]){
            // 遍历 B 的同性敌人 
            if(friendA==B) continue;// 其敌人不能是 B，不然长度不能到达 4 
            for(auto &friendB:Adj[B]){if(friendB==A) continue;// 其敌人不能是 A，不然长度不能到达 4
                if(G[friendA][friendB]==1){
                    // 找到 C 和 D
                    result.emplace_back(friendA,friendB);
                }
            }
        }
        if(result.empty()){printf("0\n");
        }else {printf("%lu\n",result.size());
            sort(result.begin(),result.end(),cmp);
            for(auto &item:result){printf("%04d %04d\n",item.first,item.second);
            }
        }
    }
    return 0;
}