【PTA】 1139 First Contact

1139 First Contact (30分)

Unlike nowadays, the way

that boys and girls expressing their feelings of love was quite subtle in the early years. When a boy A had a crush on a girl B, he would usually not contact her directly in the first place. Instead, he might ask another boy C, one of his close friends, to ask another girl D, who was a friend of both B and C, to send a message to B -- quite a long shot, isn't it? Girls would do analogously.

Here given a network of friendship relations, you are supposed to help a boy or a girl to list all their friends who can possibly help them making the first contact.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N (1 < N ≤ 300) and M, being the total number of people and the number of friendship relations, respectively. Then M lines follow, each gives a pair of friends. Here a person is represented by a 4-digit ID. To tell their genders, we use a negative sign to represent girls.

After the relations, a positive integer K (≤ 100) is given, which is the number of queries. Then K lines of queries follow, each gives a pair of lovers, separated by a space. It is assumed that the first one is having a crush on the second one.

Output Specification:

For each query, first print in a line the number of different pairs of friends they can find to help them, then in each line print the IDs of a pair of friends.

If the lovers A and B are of opposite genders, you must first print the friend of A who is of the same gender of A, then the friend of B, who is of the same gender of B. If they are of the same gender, then both friends must be in the same gender as theirs. It is guaranteed that each person has only one gender.

The friends must be printed in non-decreasing order of the first IDs, and for the same first ones, in increasing order of the seconds' ones.

 

 

题意解析：

    在遥远的过去，如果一个男孩子（♂）喜欢一个女孩子（♀），需要经过漫长的朋友转述才能进行第一次约会。例如李雷雷（♂）如果喜欢韩梅梅（♀），那么他需要通过告诉他的小伙伴赵壮壮（♂），再由赵壮壮告诉韩梅梅的小伙伴刘乐乐（♀）,注意赵壮壮和刘乐乐也必须是好友才可以哦，这样李雷雷才能可以韩梅梅进行First Contact。那么通过你聪明的脑袋设计一个简单的方案让巴斯光年帮助这些童鞋进行First contact吧。

 

注意，由于来自遥远外星的巴斯光年的思维模式和我们不一样，你需要将整个问题拆解成具体实践方式，这样巴斯光年才能理解哦！

 

图3 巴斯光年“飞向宇宙,浩瀚无垠!”

 

解题思路：

 

对于一个简单的朋友圈假设我们用红色的大圆代表心动男生，蓝色的大圆代表心动女生，红色的小圆代表心动男生好友，蓝色的小圆代表女生好友。

 

     1.由于题目要求限制，我们首先得把朋友圈里的异性好友都给删掉。

 

     2.逐一询问剩下的好友（a,b,c,d），你认识（e,f,g,h）其中之一吗？:

         

     3.如果有一个反馈是Yes!的那么你就成功啦！

 

 

对于这样一个方案，你觉得是能处理了每一个Case吗？（提示：同行爱恋同学会不会存在问题？）另外对于这个问题你还有其他的方案吗？如果有，存在更加合理有效的方法吗？欢迎留言讨论

 

如果你已经彻底理解了这个问题，咱们来试试利用手中代码去解决这个问题吧！

（题目源自PTA甲级）

https://pintia.cn/problem-sets/994805342720868352/problems/994805344776077312

 
#include iostream
#include vector

using namespace std;

#define MaxData 10001

int find(int num);
void UNION(int n1, int n2);
int parents[MaxData];

int main()
{
	for (int i = 0; i  MaxData; i++) parents[i] = -1;
	int N;
	cin  N;
	vectorvectorint pictures;
	int maxSize=0;
	for (int i = 0; i  N; i++) {
		int number;
		cin  number;
		vectorint tmpPic;
		for (int j = 0; j  number; j++) {
			int index;
			cin  index;
			if (index  maxSize) maxSize = index;
			tmpPic.push_back(index);
		}
		for (int j = 1; j  number; j++) {
			UNION(tmpPic[j - 1], tmpPic[j]);
		}
		pictures.push_back(tmpPic);
	}
	int Q;
	cin  Q;
	int  query;
	query = new int[Q];
	for (int i = 0; i  Q; i++) {
		query[i] = new int[2];
	}
	for (int i = 0; i  Q; i++) {
		cin  query[i][0]  query[i][1];
	}

	int cnt = 0;
	for (int i = 1; i = maxSize; i++) {
		if (parents[i]  0)cnt++;
	}
	cout  cnt ' ' maxSizeendl;

	for (int i = 0; i  Q; i++) {
		if (find(query[i][0]) == find(query[i][1])) cout  Yes  endl;
		else cout  No  endl;
	}
    return 0;
}

int find(int num) {
	if (parents[num]  0)return num;
	return find(parents[num]);
}
void UNION(int n1, int n2) {
	int root1 = find(n1);
	int root2 = find(n2);
	if (parents[root1]  parents[root2]) {
		parents[root1] += parents[root2];
		parents[root2] = root1;
	}
	else {
		parents[root2] += parents[root1];
		parents[root1] = root2;
	}
}

（后台回复：PAT1139  获得题解AC代码）