算法1 模拟
时间复杂度O(n)
单链表模拟时可以用这个数据结构
代码1
单链表模拟用y总的模板更方便!!!
#include<bits/stdc++.h>
#define pb push_back
#define pp poop_back
#define se second
#define fi first
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=200010,mod=1e9+7;
int e[N],ne[N];
int st[N];
int main()
{
vector<int> h1;
vector<int> h2;
int n,head;
cin>>head>>n;
for(int i=1;i<=n;i++)
{
int a,b,c;
cin>>a>>b>>c;
e[a]=b;
ne[a]=c;
}
for(int i=head;i!=-1;i=ne[i])
{
int val=abs(e[i]);
if(st[val]==0)
{
st[val]=1;
h1.pb(i);
}
else
{
h2.pb(i);
}
}
for(int i=0;i<h1.size();i++)
{
if(i!=h1.size()-1)
printf("%05d %d %05d\n",h1[i],e[h1[i]],h1[i+1]);
else
printf("%05d %d -1\n",h1[i],e[h1[i]]);
}
for(int i=0;i<h2.size();i++)
{
if(i!=h2.size()-1)
printf("%05d %d %05d\n",h2[i],e[h2[i]],h2[i+1]);
else
printf("%05d %d -1",h2[i],e[h2[i]]);
}
return 0;
}
代码2 在PAT上有一个数据过不了也不知道为啥
#include<bits/stdc++.h>
#define pb push_back
#define pp poop_back
#define se second
#define fi first
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=200010,mod=1e9+7;
struct Node{
int val,to;
}q[N];
int mp[N];
int st[N];
int main()
{
vector<int> h;
int n,head;
cin>>head>>n;
for(int i=1;i<=n;i++)
{
int a,b,c;
cin>>a>>b>>c;
q[a]={b,c};
mp[c]=a;
}
int next=head;
while(next!=-1)
{
int x= q[next].val >= 0 ? q[next].val : -q[next].val;
//if(x==39) cout<<next<<"$$$$$$$$$"<<endl;
if(st[x]==0)
{
//if(x==39) cout<<next<<"$$$$$$$$$"<<endl;;
st[x]=1;
}
else
{
int per=mp[next];
q[per].to=q[next].to;
h.pb(next);
mp[q[next].to]=per;
}
next=q[next].to;
}
next=head;
while(next!=-1)
{
if(q[next].to!=-1)
printf("%05d %d %05d\n",next,q[next].val,q[next].to);
else
printf("%05d %d -1\n",next,q[next].val);
next=q[next].to;
}
int len=h.size();
for(int i=0;i<len;i++)
{
int dis=h[i];
if(i!=len-1)
{
printf("%05d %d %05d\n",dis,q[dis].val,h[i+1]);
}
else
{
printf("%05d %d -1",dis,q[dis].val);
}
}
return 0;
}