题目粗心:
一张人际关系网络图,而后给出一对情侣 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;
}