我们可以用两个单链表来维护整个奶牛序列,分别对应奇数序列和偶数序列,输出时交叉输出即可,用并查集来维护两个序列的开头,其中一个开头必然是0,再找到另一个序列的开头即可
由于我对并查集进行了初始化,所以时间复杂度提高了不少,通过用了511ms
#include <iostream>
#include <vector>
using namespace std;
const int N = 1000010;
int ne[N], p[N];
vector<int> a;
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
int n;
cin >> n;
int l, r;
int st1, st2;
for (int i = 0; i < N; i ++ ) p[i] = i;
while (n -- )
{
scanf("%d %d", &l, &r);
ne[l] = r;
if (r != 0) p[r] = find(l);
a.push_back(l);
}
st2 = ne[0];
for (int i = 0; i < a.size(); i ++ )
if (find(a[i]) != 0)
{
st1 = find(a[i]);
break;
}
while (st1)
{
printf("%d ", st1);
if (st2) printf("%d ", st2);
st1 = ne[st1];
st2 = ne[st2];
}
return 0;
}
我进行了一些优化,用时439ms,希望有大佬再优化一下
#include <iostream>
#include <vector>
using namespace std;
const int N = 1000010;
int ne[N], p[N];
vector<int> a;
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
int n;
cin >> n;
int l, r;
int st1, st2;
// for (int i = 0; i < N; i ++ ) p[i] = i;
while (n -- )
{
scanf("%d %d", &l, &r);
l ++ ; r ++ ;
ne[l] = r;
if (p[l] == 0) p[l] = l;
if (r != 1) p[r] = find(l);
a.push_back(l);
}
st2 = ne[1];
for (int i = 0; i < a.size(); i ++ )
if (find(a[i]) != 1)
{
st1 = find(a[i]);
break;
}
while (st1 > 1)
{
printf("%d ", st1 - 1);
if (st2 > 1) printf("%d ", st2 - 1);
st1 = ne[st1];
st2 = ne[st2];
}
return 0;
}
最终优化如下