Set Construction (Codeforces 1761C)
Tags: Greedy, graphs

You are given a binary matrix $$$b$$$ (all elements of the matrix are $$$0$$$ or $$$1$$$) of $$$n$$$ rows and $$$n$$$ columns.You need to construct a $$$n$$$ sets $$$A_1, A_2, \ldots, A_n$$$, for which the following conditions are satisfied:  Each set is nonempty and consists of distinct integers between $$$1$$$ and $$$n$$$ inclusive.  All sets are distinct.  For all pairs $$$(i,j)$$$ satisfying $$$1\leq i, j\leq n$$$, $$$b_{i,j}=1$$$ if and only if $$$A_i\subsetneq A_j$$$. In other words, $$$b_{i, j}$$$ is $$$1$$$ if $$$A_i$$$ is a proper subset of $$$A_j$$$ and $$$0$$$ otherwise. Set $$$X$$$ is a proper subset of set $$$Y$$$, if $$$X$$$ is a nonempty subset of $$$Y$$$, and $$$X \neq Y$$$.It's guaranteed that for all test cases in this problem, such $$$n$$$ sets exist. Note that it doesn't mean that such $$$n$$$ sets exist for all possible inputs.If there are multiple solutions, you can output any of them.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t\le 1000$$$) — the number of test cases. The description of test cases follows.The first line contains a single integer $$$n$$$ ($$$1\le n\le 100$$$).The following $$$n$$$ lines contain a binary matrix $$$b$$$, the $$$j$$$-th character of $$$i$$$-th line denotes $$$b_{i,j}$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.It's guaranteed that for all test cases in this problem, such $$$n$$$ sets exist. 

Output: For each test case, output $$$n$$$ lines.For the $$$i$$$-th line, first output $$$s_i$$$ $$$(1 \le s_i \le n)$$$  — the size of the set $$$A_i$$$. Then, output $$$s_i$$$ distinct integers from $$$1$$$ to $$$n$$$  — the elements of the set $$$A_i$$$.If there are multiple solutions, you can output any of them.It's guaranteed that for all test cases in this problem, such $$$n$$$ sets exist. 

Note: In the first test case, we have $$$A_1 = \{1, 2, 3\}, A_2 = \{1, 3\}, A_3 = \{2, 4\}, A_4 = \{1, 2, 3, 4\}$$$. Sets $$$A_1, A_2, A_3$$$ are proper subsets of $$$A_4$$$, and also set $$$A_2$$$ is a proper subset of $$$A_1$$$. No other set is a proper subset of any other set.In the second test case, we have $$$A_1 = \{1\}, A_2 = \{1, 2\}, A_3 = \{1, 2, 3\}$$$. $$$A_1$$$ is a proper subset of $$$A_2$$$ and $$$A_3$$$, and $$$A_2$$$ is a proper subset of $$$A_3$$$.

Sample Inputs:
2
4
0001
1001
0001
0000
3
011
001
000

Sample Outputs:
3 1 2 3
2 1 3
2 2 4
4 1 2 3 4
1 1
2 1 2
3 1 2 3

Solution (Python):
def solve():
    n = int(input())
    sets = [[i + 1] for i in range(n)]
    for i in range(n):
        s = input()
        for j in range(n):
            if s[j] == '1':
                sets[j].append(i + 1)
    for set in sets:
        print(len(set), end=' ')
        print(' '.join([str(num) for num in set]))
for t in range(int(input())):
    solve()

Solution (Python):
t = int(input())

def solve():
    n = int(input())
    res = [[] for _ in range(n)]
    for i in range(n):
        s = input()
        res[i].append(i + 1)
        for (j, c) in enumerate(s):
            if c == '1':
                res[j].append(i + 1)
    for x in res:
        print(len(x), end=' ')
        print(' '.join(map(str, x)))
for i in range(t):
    solve()

Solution (Python):
from sys import stdin, stdout
for _ in range(int(input())):
    b = zip(*[stdin.readline().strip() for _ in range(int(input()))])
    i = 0
    for x in b:
        ri = [str(j + 1) for (j, s) in enumerate(x) if i == j or s == '1']
        print(len(ri), ' '.join(ri), sep=' ', end='\n')
        i += 1