pat 1139 First Contact (30分) 题目详解

这道题目给的输入数据 18条，如果没看懂题目意思，去把input数据关系图画出来再分析output，是非常麻烦的（我试过画出18组关系图，非常混乱），然后参考的别的大佬的代码。

其实这道题目的题目意思，在开头引言已经说明白了，题目意思大致如下：

如果一个人A，喜欢一个人D，A害羞不好意思直接和D说话，A会去找A的同性好朋友B，然后B去找B的好朋友C，但是前提是C是D的同性好朋友，好绕啊。

也就是A和B是同性朋友，C和D也是同性朋友，只要B和C也是朋友，就满足条件。但要排除 A和D直接是朋友的情况。

那么我们在处理输入的时候，只要把同性朋友存下来，然后用maps去存朋友关系（不管同性异性），因为要留着去判断B和C是否是朋友关系。

但要注意一点就是，开始输入18对关系是，不能去用int输入，用string输入，因为-0000，和+0000 int输入得到的都是0，不好判断是否是同性朋友

代码如下：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int n,m,k;
vector G[10000];
map maps;

typedef struct Node{
	int a;
	int b;
}Node;

bool cmp(Node first,Node second){
	//从小到大排序	
	if(first.a != second.a){
		return first.a < second.a;
	}else{
		return first.b < second.b;
	}
}

int main(){

#if ONLINE_JUDGE
#else
	freopen("C:\\Users\\zzloyxt\\Desktop\\1.txt","r",stdin);	
#endif	
	scanf("%d %d",&n,&m);
	string a,b;
	int a_int,b_int;  //保存各自的int类型 
	while(m--){
		cin >> a >> b;	
		//将a，b转成int类型 
		sscanf(a.c_str(),"%d",&a_int);
		sscanf(b.c_str(),"%d",&b_int);
		a_int = abs(a_int); 
		b_int = abs(b_int); 
		
		if(a.length() == b.length()){   //a和b是同性朋友，都没有-号，或者都有-号 
			G[a_int].push_back(b_int);
			G[b_int].push_back(a_int);
		}
		maps[10000* a_int + b_int] = maps[10000*b_int + a_int] = 1;  //保存朋友关系 
	}
	
	scanf("%d",&k);
	while(k--){
		cin >> a >> b;	
		//将a，b转成int类型 
		sscanf(a.c_str(),"%d",&a_int);
		sscanf(b.c_str(),"%d",&b_int);
		a_int = abs(a_int); 
		b_int = abs(b_int);
		vector ans;
		for(int i=0;i

Pat

pat 1139 First Contact (30分) 题目详解

相关

SLF4J: Class path contains multiple SLF4J bindings

（八）自动化测试之selenium学习心得-Xpath选择器

SpringMVC中org.springframework.web.servlet.DispatcherServlet报红

sys.path.append("")作用

PAT乙级-1005 继续(3n+1)猜想

Linux 去掉PATH的重复路径

PAT乙级-1003 我要通过！

PAT乙级-1010 一元多项式求导

XPath JAVA用法总结及代码样例

使用jsonpath解析json内容

原型模式(Prototype Pattern)——对象的克隆

原型模式(Prototype Pattern)——对象的克隆

标签