Problem:

Problem E: Map of Ninja House

An old document says that a Ninja House in Kanazawa City was in fact a defensive fortress, which was designed like a maze. Its rooms were connected by hidden doors in a complicated manner, so that any invader would become lost. Each room has at least two doors.

The Ninja House can be modeled by a graph, as shown in Figure l. A circle represents a room. Each line connecting two circles represents a door between two rooms. 

Figure l. Graph Model of Ninja House.

Figure 2. Ninja House exploration.

I decided to draw a map, since no map was available. Your mission is to help me draw a map from the record of my exploration.

I started exploring by entering a single entrance that was open to the outside. The path I walked is schematically shown in Figure 2, by a line with arrows. The rules for moving between rooms are described below.

    After entering a room, I first open the rightmost door and move to the next room. However, if the next room has already been visited, I close the door without entering, and open the next rightmost door, and so on. When I have inspected all the doors of a room, I go back through the door I used to enter the room. 

I have a counter with me to memorize the distance from the first room. The counter is incremented when I enter a new room, and decremented when I go back from a room. In Figure 2, each number in parentheses is the value of the counter when I have entered the room, i.e., the distance from the first room. In contrast, the numbers not in parentheses represent the order of my visit.

I take a record of my exploration. Every time I open a door, I record a single number, according to the following rules.

   
 If the opposite side of the door is a new room, I record the number of doors in that room, which is a positive number.

   
 If it is an already visited room, say R, I record ``the distance of R from the first room'' minus ``the distance of the current room from the first room'', which is a negative number.

In the example shown in Figure 2, as the first room has three doors connecting other rooms, I initially record ``3''. Then when I move to the second, third, and fourth rooms, which all have three doors, I append ``3 3 3'' to the record. When I skip the entry from the fourth room to the first room, the distance difference ``-3'' (minus three) will be appended, and so on. So, when I finish this exploration, its record is a sequence of numbers ``3 3 3 3 -3 3 2 -5 3 2 -5 -3''.

There are several dozens of Ninja Houses in the city. Given a sequence of numbers for each of these houses, you should produce a graph for each house. 

Input

The first line of the input is a single integer n, indicating the number of records of Ninja Houses I have visited. You can assume that n is less than 100. Each of the following n records consists of numbers recorded on one exploration and a zero as a terminator. Each record consists of one or more lines whose lengths are less than 1000 characters. Each number is delimited by a space or a newline. You can assume that the number of rooms for each Ninja House is less than 100, and the number of doors in each room is less than 40.

Output

For each Ninja House of m rooms, the output should consist of m lines. The j-th line of each such m lines should look as follows:

i r1 r2  ... rki

where r1, ... , rki should be rooms adjoining room i, and ki should be the number of doors in room i. Numbers should be separated by exactly one space character. The rooms should be numbered from 1 in visited order. r1, r2, ... , rki should be in ascending order. Note that the room i may be connected to another room through more than one door. In this case, that room number should appear in r1, ... , rki as many times as it is connected by different doors.

Sample Input

2
3 3 3 3 -3 3 2 -5 3 2 -5 -3 0
3 5 4 -2 4 -3 -2 -2 -1 0

Output for the Sample Input

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



Sample input:
2
3 3 3 3 -3 3 2 -5 3 2 -5 -3 0
3 5 4 -2 4 -3 -2 -2 -1 0


Sample output:
1 2 4 6
2 1 3 8
3 2 4 7
4 1 3 5
5 4 6 7
6 1 5
7 3 5 8
8 2 7
1 2 3 4
2 1 3 3 4 4
3 1 2 2 4
4 1 2 2 3

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def solve():
    record = list(map(int,input().split()))
    while record[-1] != 0:
        record += list(map(int,input().split()))
    number_of_room = sum(1 if r > 0 else 0 for r in record) + 1
    G = [[] for _ in range(number_of_room)]
    deg = [0] * number_of_room
    parents = [-1] * number_of_room
    dist = [1000] * number_of_room
    dist[1] = 0

    now = 1
    cnt = 0
    for r in record[:-1]:
        if r > 0:
            cnt += 1
            if cnt > 1:
                G[cnt].append(now)
                G[now].append(cnt)
                deg[now] -= 1
                dist[cnt] = dist[now] + 1
                parents[cnt] = now
                deg[cnt] = r - 1
            else:
                deg[cnt] = r
            now = cnt
            while deg[now] <= 0 and now >= 0:
                now = parents[now]
        else:
            i = parents[now]
            while True:
                if dist[i] - dist[now] == r:
                    G[now].append(i)
                    G[i].append(now)
                    deg[i] -= 1
                    deg[now] -= 1
                    while deg[now] <= 0 and now >= 0:
                        now = parents[now]
                    break
                i = parents[i]
    
    for i in range(1,number_of_room):
        G[i].sort()
        print(i,*G[i])      

def main():
    N = int(input())
    for _ in range(N):
        solve()
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
for i in range(N):
    L = []
    while 1:
        *s, = map(int, input().split())
        if s[-1] == 0:
            L.extend(s[:-1])
            break
        L.extend(s)
    G = []
    st = []
    cur = 0
    for s in L:
        if s > 0:
            G.append([])
            if st:
                u = [cur, s-1]
                v = st[-1]
                v[1] -= 1
                G[u[0]].append(v[0])
                G[v[0]].append(u[0])
                st.append(u)
                while st and st[-1][1] == 0:
                    st.pop()
            else:
                st.append([cur, s])
            cur += 1
            continue
        u = st[s-1]; u[1] -= 1
        v = st[-1]; v[1] -= 1
        G[u[0]].append(v[0])
        G[v[0]].append(u[0])
        while st and st[-1][1] == 0:
            st.pop()
    for i, vs in enumerate(G):
        vs.sort()
        print(i+1, *map(lambda x: x+1, vs))

Submission status: Accepted

Solution code:
#1236
q=int(input())
for _ in range(q):
    data=[]
    while 1:
        data+=list(map(int,input().split()))
        if data[-1]==0:
            break
    rooms=[(-1,1,[])]
    now=0
    i=0
    st=[]
    counter=[-1 for i in range(1000)]
    while data[i]!=0:
        while rooms[now][1]<=len(rooms[now][2]):
            now=st.pop()
        if data[i]>0:
            rooms.append((rooms[now][0]+1,data[i]+(1 if i==0 else 0),[]))
            counter[rooms[now][0]+1]=len(rooms)-1
            rooms[now][2].append(len(rooms)-1)
            rooms[len(rooms)-1][2].append(now)
            if len(rooms[now][2])<rooms[now][1]:
                st.append(now)
            now=len(rooms)-1
        elif data[i]<0:
            nxt=counter[rooms[now][0]+data[i]]
            rooms[nxt][2].append(now)
            rooms[now][2].append(nxt)
        i+=1
    for i in range(1,len(rooms)):
        print(i,end='')
        for e in sorted(rooms[i][2]):
            if e==0:
                continue
            print('',e,end='')
        print()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f():
        a = LI()
        while a[-1] != 0:
            a += LI()
        r = [[]]
        c = 0
        nk = [a[0]]
        d = {}
        d[0] = 0
        for n in a[1:]:
            if n == 0:
                break
            while nk[d[c]] < 1:
                c -= 1

            if n < 0:
                dc = d[c]
                dn = d[c+n]
                r[dn].append(dc)
                r[dc].append(dn)
                nk[dn] -= 1
                nk[dc] -= 1
            else:
                nk.append(n-1)
                dc = d[c]
                ni = len(nk) - 1
                r[dc].append(ni)
                r.append([dc])
                nk[dc] -= 1
                c += 1
                d[c] = ni
        rr = []
        for i in range(len(nk)):
            rr.append('{} {}'.format(i+1, ' '.join(map(lambda x: str(x+1), sorted(r[i])))))
        return '\n'.join(rr)

    while 1:
        n = I()
        if n == 0:
            break
        rr = [f() for _ in range(n)]
        break

    return '\n'.join(map(str, rr))


print(main())