欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

1139 First Contact ——和柳神差不多快,但我比她空间占用更少

程序员文章站 2024-03-23 17:42:40
...

分析

给出关系网;给出任意2个人,得到各自2个同性朋友,且这2个人之间也是朋友

进一步分析

  • 由于存在 -0000 和 0000 必然用string,因此用到map 建立邻接表
  • 其次由于需要 判断2个人之间也是朋友——》相连

为了达到更好的时间效率,因此用map+set建图

别问我怎么知道map+vector不行的

  • 同性判断,因此也只需比较string的长度即可

输出时:

  1. 要求是去绝对值,因此用substr进行截断
  2. 其次要求第一个升序,相同时,第二个也升序
    因此采用map+set自身有序的特点来进行存放

其他注意

给出a,b;a朋友是c,b朋友是d

存在c就是b的情况,即找到的朋友恰好就是需要判断伴侣,因此要排除该情况

代码

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;

int vertex, edge, times;
unordered_map<string, set<string>> graph;

void InPut();
void Judge(map<string, set<string>>);
int main() {
	InPut();
	map<string, set<string>>print;
	for (int i = 0; i < times; i++)
		Judge(print);
	return 0;
}
void InPut() {
	scanf("%d %d", &vertex, &edge);
	string x, y;
	for (int i = 0; i < edge; i++) {
		cin >> x >> y;
		graph[x].insert(y);
		graph[y].insert(x);
	}
	scanf("%d", &times);
}
void Judge(map<string, set<string>>print) {
	string x, y, a, b;
	cin >> x >> y;
	int count{ 0 };
	for (auto i = graph[x].begin(); i != graph[x].end(); i++) {
		if (x.size() == (*i).size() && *i != y) {
			for (auto j = graph[y].begin(); j != graph[y].end(); j++) {
				if (y.size() == (*j).size() && *j != x) {
					if (graph[*i].find(*j) != graph[*i].end()) {
						(*i).size() == 5 ? a = (*i).substr(1, 4) : a = *i;
						(*j).size() == 5 ? b = (*j).substr(1, 4) : b = *j;
						print[a].insert(b);
						count++;
					}
				}
			}
		}
	}
	printf("%d\n", count);
	for (auto i = print.begin(); i != print.end(); i++) {
		for (auto j : print[i->first]) {
			cout << i->first << " " << j << "\n";
		}
	}
}

我的版本

1139 First Contact ——和柳神差不多快,但我比她空间占用更少

柳神的版本

1139 First Contact ——和柳神差不多快,但我比她空间占用更少

后记

其他可优化处

由于需要每次找同性朋友,因此可以分开建2个男性和女性表,来专门进行查同性朋友

不过肯定会牺牲空间和书写效率

换取时间效率

错误写法

一定一定不要写出这种东西,一个测试点都过不去;血的教训

cout << i->first << ends;
cout << j << endl;

 

相关标签: 数据结构题目