| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3845 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3630 |
| 4 | orzdevinwang | 3573 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | jqdai0815 | 3532 |
| 8 | ecnerwala | 3501 |
| 9 | gyh20 | 3447 |
| 10 | Rebelz | 3409 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | adamant | 163 |
| 3 | awoo | 161 |
| 4 | maroonrk | 152 |
| 4 | nor | 152 |
| 6 | -is-this-fft- | 151 |
| 7 | TheScrasse | 148 |
| 8 | atcoder_official | 146 |
| 9 | Petr | 145 |
| 10 | pajenegod | 144 |
Constraints:
Size of the array: [1 10^5]
Element: 1 <= a[i] <= 10^6
Brute force won't work because of the constraints. I tried thinking of various ways but all were convoluted. I feel there is an easier way to think about it but I am missing some observation.
Any help would be highly appreciated.
Thanks!
You can use graph to solve this problem, put an edge between each element of each pair .
How will you do it in O(n)?
Draw an undirected edge between every element in the pair. You know that the ends of the array must have degree 1, as they are only adjacent to 1 element. Just find any node with degree 1, run a dfs from there, and return the order in which you visited the elements in the dfs. One other thing to note is that you can "coordinate-compress" the values in the array, so your runtime is $$$O(N)$$$, not $$$O(N+A)$$$, where $$$A$$$ is the maximum value of an array element.
Since all the values are different we can construct a graph from the pairs. Suppose we have pair [a, b] , lets make an edge a — b. After we built the graph we can find the vertex with degree of 1 and make a simple dfs to print the array.