AcWing 4303. 链表
原题链接
中等
作者:
ywt51
,
2023-06-05 18:13:59
,
所有人可见
,
阅读 121
算法1:结构体标记(暴力枚举) $O(n^2)$
//初始每条线段都是一个单链表,结构体维护线段,标记是否被合并了,记录合并的个数
//n-合并个数就是总共出现的单链表个数,合并的时候标记 双重循环
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
struct node{
string st, ed;
bool f = 1;
}d[N];
int n;
int main() {
cin >> n;
for (int i = 0; i < n; ++ i) cin >> d[i].st >> d[i].ed;
int cnt = 0; //记录合并了几个
for (int i = 0; i < n; ++ i)
for (int j = i+1; j < n; ++ j) //遍历后面的即可
if (d[i].ed == d[j].st && d[j].f) { //dj可以合并到di后面 且没有被合并过
d[i].ed = d[j].ed;
d[j].f = 0; //标记被合并
cnt++;
}
cout << n - cnt << endl;
for (int i = 0; i < n; ++ i)
if (d[i].f)
cout << d[i].st << ' ' << d[i].ed << endl;
return 0;
}
算法2:map维护() $O(n)$
//对每个单链表维护出头和尾的对应,map维护
//每条边必然属于某一个单链表,怎么找属于那个单链表,
//判断a->b a是否是某一个单链表的尾,还需要存储一下尾到头的映射
//通过尾找到头,改变他对应的尾, 尾对应的头也要作修改
#include <bits/stdc++.h>
using namespace std;
int main() {
unordered_map<string, string> head, tail;
string a, b;
int n;
cin >> n;
while (n--) {
cin >> a >> b;
if (!tail.count(a)) head[a] = b, tail[b] = a;
else head[tail[a]] = b, tail[b] = tail[a], tail.erase(a);
}
cout << head.size() << endl;
for (auto &[k, v] : head)
cout << k << ' ' << v << endl;
return 0;
}
算法3:() $O(n^2)$
//直接用map维护出头尾映射,新边进来,直接遍历一遍map 判断是否是某一个的结尾,不是就加入
#include <bits/stdc++.h>
using namespace std;
unordered_map<string, string> mp;
int n;
string a, b;
int main() {
cin >> n;
while (n--) {
cin >> a >> b;
bool f = 1;//默认a->b是一个新的链表
for (auto& it : mp) //引用类型,要修改尾巴
if (a == it.second) {//a是否个链表的尾巴,能接上,更新该链表的尾巴
it.second = b;
f = 0;
break;
}
if (f) mp[a] = b;
}
cout << mp.size() << endl;
for (auto it : mp)
cout << it.first << ' ' << it.second << endl;
return 0;
}