codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ![](https://espresso.codeforces.com/5f1953d2774c0b1378a67cd9be1536c8978a3765.png)
     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]$.