标签：模拟，链表
Doublylinked list is one of the fundamental data structures. A doubly linked list isa sequence of elements, each containing information about the previous and thenext elements of the list. In this problem all lists have linear structure.I.e. each element except the first has exactly one previous element, eachelement except the last has exactly one next element. The list is not closed ina cycle.
In thisproblem you are given n memorycells forming one or more doubly linked lists. Each cell contains informationabout element from some list. Memory cells are numbered from 1 to n.
For eachcell i you are given twovalues:
· li — cell containing previous element for theelement in the cell i;
· ri — cell containing next element for theelement in the cell i.
If cell i contains informationabout the element which has no previous element thenli = 0.Similarly, if cell i containsinformation about the element which has no next element then ri = 0.
Three lists are shown on the picture.
Forexample, for the picture above the values of l and r are thefollowing: l1 = 4,r1 = 7; l2 = 5, r2 = 0; l3 = 0, r3 = 0; l4 = 6, r4 = 1; l5 = 0, r5 = 2; l6 = 0, r6 = 4; l7 = 1, r7 = 0.
Your taskis to unite all given lists in a single list, joining them to each other in anyorder. In particular, if the input data already contains a single list, thenthere is no need to perform any actions. Print the resulting list in the formof values li, ri.
Any otheraction, other than joining the beginning of one list to the end of another, cannot be performed.
Input
The firstline contains a single integer n (1 ≤ n ≤ 100) — the number ofmemory cells where the doubly linked lists are located.
Each ofthe following n linescontains two integers li, ri (0 ≤ li, ri ≤ n) — thecells of the previous and the next element of list for cell i. Value li = 0 if element in cell i has no previouselement in its list. Value ri = 0 if elementin cell i has no next elementin its list.
It isguaranteed that the input contains the correct description of a single or moredoubly linked lists. All lists have linear structure: each element of listexcept the first has exactly one previous element; each element of list exceptthe last has exactly one next element. Each memory cell contains informationabout one element from some list, each element of each list written in one of n given cells.
Output
Print n lines, the i-th line must contain two integers li and ri — the cells of theprevious and the next element of list for cell i after all lists from the input are united ina single list. If there are many solutions print any of them.
Example
Input
7
4 7
5 0
0 0
6 1
0 2
0 4
1 0
Output
4 7
5 6
0 5
6 1
3 2
2 4
1 0
题意：给出若干个链表，你需要合并他们，使其成为一个链表的整体
分析：直接模拟就好了，注意合并的时候需要判断这两个链表是否已经连接过了，以免出现首尾相接形成环的错误现象
Code
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int n,l[505],r[505],cnt=0;
inline bool checkl(int x,int y)
{
if(l[x]==0)return1;
elseif(l[x]==y)return 0;
returncheckl(l[x],y);
}
inline bool checkr(int x,int y)
{
if(r[x]==0)return1;
elseif(r[x]==y)return 0;
returncheckr(r[x],y);
}
int main()
{
scanf("%d",&n);
rep(i,1,n){scanf("%d%d",&l[i],&r[i]);if(l[i]==0)cnt++;}
rep(i,1,n){
// cout<<cnt<<endl;
if(l[i]==0&&cnt>1)
rep(j,1,n)if(r[j]==0&&i!=j&&checkr(i,j)){r[j]=i;l[i]=j;cnt--;break;}
if(r[i]==0&&cnt>1)
rep(j,1,n)if(l[j]==0&&i!=j&&checkl(i,j)&&checkr(i,j)){l[j]=i;r[i]=j;cnt--;break;}
}
rep(i,1,n)printf("%d%d\n",l[i],r[i]);
return0;
}
