Link Sub: http://www.spoj.com/PTIT/problems/P151PROG/
Người Gửi: Dương Lee
- Problem:
Trong giờ ăn trưa tại Học viên Công nghệ Bưu chính Viễn thông, có n sinh viên đang xếp hang để lấy đồ. Cảm thấy chán vì phải đứng đợi một mình, vì vậy mỗi sinh viên viết ra mã sinh viên của mình đứng ngay trước và ngay sau của mình. Nếu không có ai đứng trước hoặc không có ai đứng sau thì viết ra 0.
Đột nhiên, xe chở nước sôi đi qua, tất cả sinh viên phải tránh. Khi họ trở lại, họ không nhớ vị trí của mình mà chỉ nhớ mã sinh viên của người đừn trước và người đứng sau.
Hãy giúp các sinh viên PTIT tìm lại vị trí của mình!!!!
Input
Dòng đầu tiên gồm số tự nhiên n (2 ≤ n ≤ 2·10^5) – số lượng sinh viên.
n dòng tiếp theo, dòng thứ i gồm cặp số tự nhiên ai, bi (0 ≤ ai, bi ≤ 10^6), với ai là mã sinh viên của người đứng trước, bi là mã sinh viên của người đứng sau 1 sinh viên nào đó. Nếu không có ai đứng trước hoặc không có ai đứng sau nhập 0.
Mã sinh viên của mỗi sinh viên là khác nhau.
Output
Trên 1 dòng, in ra n số x1, x2, ..., xn , danh sách của các sinh viên theo thứ tự ban đầu.
Example:
Trên 1 dòng, in ra n số x1, x2, ..., xn , danh sách của các sinh viên theo thứ tự ban đầu.
Input
4
92 31
0 7
31 0
7 141
Output:
92 7 31 141
- Solution:
Bài này sẽ có hai trường hợp chính:
- n lẻ, dãy VD: 7 8 6
biểu diễn input là:
0 8
7 6
8 0
-> Sử dụng mảng đánh dấu ta lưu lại được 2 dãy liên kết:
+ arr[0] = 8, arr[8] = 0 -> truy vết thu được: D1: 8 (0 không tính vào dãy)
+ arr[6] = 7, arr[7] = -1 -> truy vết thu được: D2: 6 7 (Ở đây tìm được 6 là số cuỗi dãy 2 vì sau 6 không còn số nào liên kết với nó)
-> In D2 và D1 xen kẽ: 7 8 6 (D1 in thuận, D2 in ngược).
- n chẵn, dãy VD: 7 8 6 1
biểu diễn input là:
0 8
7 6
8 1
6 0
-> Sử dụng mảng đánh dấu ta lưu lại được 2 dãy liên kết:
+ arr[0] = 8, arr[8] = 1, arr[1]=-1 (=-1 là khởi tạo để kết thúc kết nối)
-> truy vết thu được: D1: 8 1
+ arr[0] = 6, arr[6] = 7, arr[7]=-1 (=-1 là khởi tạo để kết thúc kết nối)
-> truy vết thu được: D2: 6 7
-> In D2 và D1 xen kẽ: 7 8 6 1 (D1 in thuận, D2 in ngược).
- Code:
C++:
https://ideone.com/HVFFEX
#include <iostream>
#include <vector>
using namespace std;
int SV_sau[1000006];
int SV_truoc[1000006];
void init ()
{
for (int i=0; i<=1000000; i++)
{
SV_sau[i]=-1;
SV_truoc[i]=-1;
}
}
vector <int> so;
int dd[1000006] = {0};
void check (int x)
{
if (dd[x]==0 && x!=0)
{
so.push_back(x);
dd[x]=1;
}
}
int main ()
{
init ();
int n;
cin>>n;
int vt1, vt2;
for (int i=1; i<=n; i++)
{
int a, b;
cin>>a>>b;
check (a); check (b);
SV_sau[a] = b;
SV_truoc[b] = a;
}
vector <int> D1;
vector <int> D2;
if (n%2==0)
{
//Day 1
int st = 0;
while (1)
{
if (SV_sau[st]==-1) break;
D1.push_back(SV_sau[st]);
st = SV_sau[st];
}
// Day 2
st = 0;
while (1)
{
if (SV_truoc[st]==-1) break;
D2.push_back(SV_truoc[st]);
st = SV_truoc[st];
}
//IN
int D_1 = 0, D_2 = D2.size()-1;
for (int i=1; i<=n; i++)
{
if (i%2!=0)
{
cout<<D2[D_2]<<" ";
D_2--;
}
else
{
cout<<D1[D_1]<<" ";
D_1++;
}
}
}
else
{
//Day 1
int st = 0;
while (1)
{
if (SV_sau[st]==0) break;
D1.push_back(SV_sau[st]);
st = SV_sau[st];
}
st=0;
for (int i=0; i<so.size(); i++)
{
if (SV_sau[so[i]]==-1)
{
st=so[i];
break;
}
}
if (st!=0) D2.push_back(st);
while (1)
{
if (SV_truoc[st]==-1) break;
D2.push_back(SV_truoc[st]);
st = SV_truoc[st];
}
int D_1 = 0, D_2 = D2.size()-1;
for (int i=1; i<=n; i++)
{
if (i%2!=0)
{
cout<<D2[D_2]<<" ";
D_2--;
}
else
{
cout<<D1[D_1]<<" ";
D_1++;
}
}
}
return 0;
}