1139 First Contact ——和柳神差不多快,但我比她空间占用更少
程序员文章站
2024-03-23 17:42:40
...
分析
给出关系网;给出任意2个人,得到各自2个同性朋友,且这2个人之间也是朋友
进一步分析
- 由于存在 -0000 和 0000 必然用string,因此用到map 建立邻接表
- 其次由于需要 判断2个人之间也是朋友——》相连
为了达到更好的时间效率,因此用map+set建图
(别问我怎么知道map+vector不行的)
- 同性判断,因此也只需比较string的长度即可
输出时:
- 要求是去绝对值,因此用substr进行截断
- 其次要求第一个升序,相同时,第二个也升序
因此采用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", ×);
}
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";
}
}
}
我的版本
柳神的版本
后记
其他可优化处
由于需要每次找同性朋友,因此可以分开建2个男性和女性表,来专门进行查同性朋友
不过肯定会牺牲空间和书写效率
换取时间效率
错误写法
一定一定不要写出这种东西,一个测试点都过不去;血的教训
cout << i->first << ends;
cout << j << endl;
上一篇: mysql之同表复制插入数据
下一篇: python之如何发送邮件