题目链接

题目：

Bob is an avid fan of the video game “League of Leesins”, and today he celebrates as the League of Leesins World Championship comes to an end!

The tournament consisted of n (n≥5) teams around the world. Before the tournament starts, Bob has made a prediction of the rankings of each team, from 1-st to n-th. After the final, he compared the prediction with the actual result and found out that the i-th team according to his prediction ended up at the pi-th position (1≤pi≤n, all pi are unique). In other words, p is a permutation of 1,2,…,n.

As Bob’s favorite League player is the famous “3ga”, he decided to write down every 3 consecutive elements of the permutation p. Formally, Bob created an array q of n−2 triples, where qi=(pi,pi+1,pi+2) for each 1≤i≤n−2. Bob was very proud of his array, so he showed it to his friend Alice.

After learning of Bob’s array, Alice declared that she could retrieve the permutation p even if Bob rearranges the elements of q and the elements within each triple. Of course, Bob did not believe in such magic, so he did just the same as above to see Alice’s respond.

For example, if n=5 and p=[1,4,2,3,5], then the original array q will be [(1,4,2),(4,2,3),(2,3,5)]. Bob can then rearrange the numbers within each triple and the positions of the triples to get [(4,3,2),(2,3,5),(4,1,2)]. Note that [(1,4,2),(4,2,2),(3,3,5)] is not a valid rearrangement of q, as Bob is not allowed to swap numbers belong to different triples.

As Alice’s friend, you know for sure that Alice was just trying to show off, so you decided to save her some face by giving her any permutation p that is consistent with the array q she was given.

Input
The first line contains a single integer n (5≤n≤105) — the size of permutation p.

The i-th of the next n−2 lines contains 3 integers qi,1, qi,2, qi,3 (1≤qi,j≤n) — the elements of the i-th triple of the rearranged (shuffled) array qi, in random order. Remember, that the numbers within each triple can be rearranged and also the positions of the triples can be rearranged.

It is guaranteed that there is at least one permutation p that is consistent with the input.

Output
Print n distinct integers p1,p2,…,pn (1≤pi≤n) such that p is consistent with array q.

If there are multiple answers, print any.

Example
input
5
4 3 2
2 3 5
4 1 2
output
1 4 2 3 5

题目大意：

给你一个整数n，以及n-2个三元组，让你找到原序列。
例如：样例[1, 4, 2, 3, 5]，可以得到[1, 4, 2],[4, 2, 3],[2, 3, 5]。
而输入中的3个三元组则是上面的到的三个三元组随机打乱顺序。

题解：

观察可得，如果在所有三元组中只出现了一次的元素一定在开头或是结尾，只出现了两次的元素一定在第二个位置或是倒数第二个位置。我们很容易能得到前两个位置，而第三个位置能由前两个位置确定，以此类推，则能得到整个序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include<functional>
#include<algorithm>
#include<iostream>
#include<utility>
#include<climits>
#include<cstring>
#include<cstdlib>
#include<numeric>
#include<cstdio>
#include<string>
#include<vector>
#include<cctype>
#include<cmath>
#include<stack>
#include<queue>
#include<list>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const int inf88 = 1482184792;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = acos(-1.0);
typedef pair<int, int> P;
#define N 100100

int p[N][3];

int main(){
    int n;
    scanf("%d", &n);

    int cnt[N];///记录每个数出现的次数
    fill(cnt+1, cnt+n+1, 0);

    map<P, int> mp;///记录P出现的行编号

    for(int i = 1; i <= n-2; i++){
        scanf("%d%d%d", &p[i][0], &p[i][1], &p[i][2]);
        int a = p[i][0], b = p[i][1], c = p[i][2];
        cnt[a]++; cnt[b]++; cnt[c]++;
        if(mp[P(a, b)] == 0)
            mp[P(a, b)] = i;
        else
            mp[P(b, a)] = i;

        if(mp[P(a, c)] == 0)
            mp[P(a, c)] = i;
        else
            mp[P(c, a)] = i;

        if(mp[P(b, c)] == 0)
            mp[P(b, c)] = i;
        else
            mp[P(c, b)] = i;
    }

    ///找到两个出现一次的数和两个出现两次的数
    int x1 = -1, y1 = -1, x2 = -1, y2 = -1;
    for(int i = 1; i <= n; i++){
        if(cnt[i] == 3)
            continue;
        if(cnt[i] == 1){
            if(x1 == -1)
                x1 = i;
            else
                y1 = i;
        }
        else if(cnt[i] == 2){
            if(x2 == -1)
                x2 = i;
            else
                y2 = i;
        }
    }
//    调试：
//    cout << "x1 = " << x1 << endl;
//    cout << "y1 = " << y1 << endl;
//    cout << "x2 = " << x2 << endl;
//    cout << "y2 = " << y2 << endl;

    int r[N];///记录答案
    ///确定前两个数
    r[0] = -1;///用来防止i==3时出现r[i-3]未定义
    r[1] = x1;
    if(mp[P(x1, x2)] == 0 && mp[P(x2, x1)] == 0)
        r[2] = y2;
    else
        r[2] = x2;
//    调试：
//    cout << "r[1] = " << r[1] << " and r[2] = " << r[2] << endl;

    ///确定中间的数
    for(int i = 3; i <= n-2; i++){
        int pos = mp[P(r[i-1], r[i-2])];///找到当前值的位置
        int val = 0;///确定下一个值
        for(int j = 0; j < 3 && pos; j++)
            if(p[pos][j] != r[i-1] && p[pos][j] != r[i-2] && p[pos][j] != r[i-3]){
                val = p[pos][j];
                break;
            }
        if(val == 0){///如果重合
            pos = mp[P(r[i-2], r[i-1])];
            for(int j = 0; j < 3; j++)
                if(p[pos][j] != r[i-1] && p[pos][j] != r[i-2] && p[pos][j] != r[i-3]){
                    val = p[pos][j];
                    break;
                }
        }
        r[i] = val;
    }
    ///确定最后两个数
    r[n] = y1;
    if(mp[P(y1, x2)] == 0 && mp[P(x2, y1)] == 0)
        r[n-1] = y2;
    else
        r[n-1] = x2;

//    调试：
//    cout << "r[n-1] = " << r[n-1] << " and r[n] = " << r[n] << endl;
    ///输出
    for(int i = 1; i <= n; i++)
        printf("%d%c", r[i], i == n ? '\n' : ' ');
    return 0;
}
/*
7
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7

1 2 3 4 5 6 7

7
5 3 1
5 4 7
4 6 7
2 6 7
4 5 3

1 3 5 4 7 6 2
*/

反思

在比赛时并没有解出这道题，思路已经有了，但是因为一些bug而耽误了好长时间，事实上这时已经应该重构代码了，但是下不去那个狠心，导致直到比赛结束也没有解决bug，等到赛后重写了一遍就过了。我太难了。