关于算法-数据结构: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;
}