天梯赛 L2-002 链表去重
使用unordered_map记录每个地址的下一个地址,对于每个节点判断以下,已经出现过了,就放到ans数组中,其他的放到ans1中,注意遇到-1就直接结束。
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef long long ll;
const int N = 510;
const int mod = 998244353;
void solve() {
string st;
int n;
cin>>st>>n;
unordered_map<string,string> next;
unordered_map<string,int> value;
for(int i=1;i<=n;i++){
string s1,s2;
int w;
cin>>s1>>w>>s2;
next[s1] = s2;
value[s1] = w;
}
// for(auto it : next){
// cout<<it.first<<" "<<it.second<<endl;
//
// }
unordered_map<int,int> mp;//标记是否被访问
vector<pair<string,int>> ans1,ans;
string now = st;
while(now != "-1"){
int w = abs(value[now]);
if(mp[w] >= 1){
ans.push_back({now,value[now]});
}else{
// cout<<"bj"<<now<<endl;
mp[w]++;
ans1.push_back({now,value[now]});
}
now = next[now];
}
int len = ans1.size();
ans1.push_back({"-1",-1});
for(int i = 0 ; i < len; i++){
cout<<ans1[i].first<<" "<<ans1[i].second
<<" "<<ans1[i+1].first<<endl;
}
len = ans.size();
ans.push_back({"-1",-1});
for(int i = 0 ; i < len; i++){
cout<<ans[i].first<<" "<<ans[i].second
<<" "<<ans[i+1].first<<endl;
}
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tt = 1;
// cin >> tt;
while (tt--) {
solve();
}
return 0;
}