题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n)$
分别求序列的第一位和第二位
第一位通过分析在给出的两个数字中只在前面的一个数字出现,而在后面的数字中不出现
第二位通过第一个数字是0可以确定
然后可以知道它它后面的后面的数字,也就是奇偶性不变,知道第一和第二就可以补完整
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int qian[N], hou[N];
int cnt1[N],cnt2[N];
int ans[N];
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i ++)
{
int a, b;
cin >> a >> b;
qian[a] = b;
hou[b] = a;
cnt1[a] ++;
cnt2[b] ++;
}
int x = qian[0];
for(int i = 1; i <= 1000000; i ++)
{
if(cnt1[i] == 1 && cnt2[i] == 0)ans[1] = i;
else if(cnt2[i] == 1 && cnt1[i] == 0)ans[n] = i;
else continue;
}
for(int i = 2; i <= n; i += 2)
{
ans[i] = x;
x = qian[x];
//cout << ans[i] << ' ';
}
x = qian[ans[1]];
for(int i = 3; i <= n; i += 2)
{
ans[i] = x;
x = qian[x];
}
for(int i = 1; i <= n; i ++)
{
cout << ans[i] << " ";
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla