2056B.md (2984B)
1 Source: https://codeforces.com/problemset/problem/2056/B 2 3 B. Find the Permutation 4 5 time limit per test 6 7 1.5 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an undirected graph with $n$ vertices, labeled from $1$ to $n$. This graph encodes a hidden permutation$^{\text{∗}}$ $p$ of size $n$. The graph is constructed as follows: 22 23 * For every pair of integers $1 \le i \lt j \le n$, an undirected edge is added between vertex $p_i$ and vertex $p_j$ if and only if $p_i \lt p_j$. Note that the edge is not added between vertices $i$ and $j$, but between the vertices of their respective elements. Refer to the notes section for better understanding. 24 25 Your task is to reconstruct and output the permutation $p$. It can be proven that permutation $p$ can be uniquely determined. 26 27 $^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array). 28 29 Input 30 31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows. 32 33 The first line of each test case contains a single integer $n$ ($1 \le n \le 1000$). 34 35 The $i$-th of the next $n$ lines contains a string of $n$ characters $g_{i, 1}g_{i, 2}\ldots g_{i, n}$ ($g_{i, j} = \mathtt{0}$ or $g_{i, j} = \mathtt{1}$) — the adjacency matrix. $g_{i, j} = \mathtt{1}$ if and only if there is an edge between vertex $i$ and vertex $j$. 36 37 It is guaranteed that there exists a permutation $p$ which generates the given graph. It is also guaranteed that the graph is undirected and has no self-loops, meaning $g_{i, j} = g_{j, i}$ and $g_{i, i} = \mathtt{0}$. 38 39 It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$. 40 41 Output 42 43 For each test case, output $n$ integers $p_1, p_2, \ldots, p_n$ representing the reconstructed permutation. 44 45 Example 46 47 Input 48 49 ``` 50 3 51 52 1 53 54 0 55 56 5 57 58 00101 59 60 00101 61 62 11001 63 64 00001 65 66 11110 67 68 6 69 70 000000 71 72 000000 73 74 000000 75 76 000000 77 78 000000 79 80 000000 81 ``` 82 83 Output 84 85 ``` 86 1 87 4 2 1 3 5 88 6 5 4 3 2 1 89 ``` 90 91 Note 92 93 In the first case $p = [1]$. Since there are no pairs $1 \le i \lt j \le n$, there are no edges in the graph. 94 95 The graph in the second case is shown below. For example, when we choose $i = 3$ and $j = 4$, we add an edge between vertices $p_i = 1$ and $p_j = 3$, because $p_i \lt p_j$. However, when we choose $i = 2$ and $j = 3$, $p_i = 2$ and $p_j = 1$, so $p_i \lt p_j$ doesn't hold. Therefore, we don't add an edge between $2$ and $1$. 96 97  98 99 In the third case, there are no edges in the graph, so there are no pairs of integers $1 \le i \lt j \le n$ such that $p_i \lt p_j$. Therefore, $p = [6, 5, 4, 3, 2, 1]$.