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