1139. First Contact (30)

题目:

1139. First Contact (30)

大概描述:

两人进行交往,注意并不只考虑异性,也考虑同性

特征词:

STL 模拟

使用语言:

C++

解题思想:

用map建立两个关系,一个是同性联系的map,一个是异性联系的map,而没有使用邻接表,化成两个map处理起来比较方便,直观

题目得分:

18

提交次数:

2

时间

60

代码

#include<map>
#include<cstdio>
#include<set>//利用set自动排序
using namespace std;

//建两个map进行存储
int main(){
 int a,b,c,e1,e2;

 map<int,set<int>> same;
 map<int,set<int>> diff;

 scanf("%d %d",&a,&b);

 for(int i = 0;i < b;i++){
 scanf("%d %d",&e1,&e2);
 if(e1 * e2 > 0){
 same[e1].insert(e2);
 same[e2].insert(e1);
 }
 else{//-0000与0000在diff中
 diff[e1].insert(e2);
 diff[e2].insert(e1);
 }
 }

 scanf("%d",&c);
 for(int i = 0;i < c;i++){
 scanf("%d %d",&e1,&e2);
 map<int,set<int>>ans;
 int t = 0;
 if(e1 * e2 <= 0){
 for(set<int>::iterator it = same[e1].begin();it != same[e1].end();it++){
 for(set<int>::iterator itt = diff[*it].begin();itt != diff[*it].end();itt++){
 if(same[e2].find(*itt) != same[e2].end() && *itt != *it){
 ans[abs(*it)].insert(abs(*itt));
 t++;
 }
 }
 }
 }else{
 for(set<int>::iterator it = same[e1].begin();it != same[e1].end();it++){
 for(set<int>::iterator itt = same[*it].begin();itt != same[*it].end();itt++){
 if(same[e2].find(*itt) != same[e2].end() && *itt != *it){
 ans[abs(*it)].insert(abs(*itt));
 t++;
 }
 }
 }


 }


 printf("%d\n",t);
 for(map<int,set<int>>::iterator it = ans.begin();it != ans.end();it++){
 for(set<int>::iterator itt = (it -> second).begin();itt != (it -> second).end();itt++){
 printf("%d %d\n",it->first,*itt);
 }
 }
 }




}

 成长

我下次一定记得用string进行读取

发表评论

电子邮件地址不会被公开。 必填项已用*标注