"""
Bethany Low
blow100
969296361
08/06/2020
COMPSCI 220 - Assignment 4
Question 2: Tree arcs and cross arcs in DFS
Programme
4
1 3
2 3
0
3
1 2
1
0
"""
#Import sys and deque library
import sys
from queue import deque
def dfs(adj):
''' Function that does a depth first search on an adjacency list
of a disgraph, returning the rank of each node in a list. '''
# Setting up queue, and visited, predecessor and rank arrays.
stack = deque()
n = len(adj)
colour = ['White']*n
pred = ['Null']*n
seen = [-1]*n
done = [-1]*n
time = 0
for i in range(0,n-1):
if colour[i] == 'White':
dfsvisit(stack, adj, colour, pred, seen, done, time, i)
return seen, done, pred
def dfsvisit(stack, adj, colour, pred, seen, done, time, node):
colour[node] = 'Grey'
seen[node] = time
time = time + 1
stack.append(node)
while len(stack) != 0:
u = stack[-1]
l = [i for i in adj[u] if colour[i]=='White']
if len(l)!=0:
for i in l:
colour[i]='Grey'
pred[i] = u
seen[i]=time
time = time+1
stack.append(i)
else:
stack.pop()
colour[node] = 'Black'
done[node] = time
time = time + 1
"""
def recursiveDFSvisit(stack, adj, colour, pred, seen, done, time, node):
colour[node] = 'Grey'
seen[node] = time
time = time + 1
for adj_node in adj[node]:
if colour[adj_node] == 'White':
pred[adj_node] = node
recursiveDFSvisit(stack, adj, colour, pred, seen, done, time, adj_node)
colour[node] = 'Black'
done[node] = time
time = time + 1
"""
"""
##########
def dfs(adj, node):
# Setting up queue, and visited, predecessor and rank arrays.
stack = deque()
n = len(adj)
visited = [False] * len(adj)
pred_array = [None] * len(adj)
seen = []
done = [None] * len(adj)
time = 0
# Adding Node 0 to the queue and setting visited and rank values.
stack.append(node)
visited[node] = True
seen.append(node)
time+=1
# While queue is not empty;
while len(stack) > 0:
u = stack[-1] # Peek at last item - node u.
if visited[u] != True:
seen.append(u[0])
visited[w] = True
remove_from_stack = True
for adj_node in adj[u]:
if visited[adj_node] != True:
visited[adj_node] = True
remove_from_stack = False
break
if remove_from_stack:
stack.pop()
return seen
"""
def count_arcs(adj_list, result):
tree_count = 0
cross_count = 0
#seen = [i for j in seen for i in j]
seen = result[0]
done = result[1]
pred = result[2]
for index in range(0, len(adj_list)-1):
if adj_list[index] != []:
print(index)
for j in adj_list[index]:
print(j)
if seen[index]<seen[j]<done[index]<done[j]:
tree_count +=1
print("Yes")
elif seen[j]<done[j]<seen[index]<done[index]:
cross_count +=1
print("yes")
return(str(tree_count) +","+ str(cross_count))
#Main Programme - While Loop;
while True:
# Get the order of the digraph.
order = int(sys.stdin.readline())
# If system reads in zero, then stop programme.
if order == 0:
break
# Read in each adjacency list
adj_list = [[] for i in range(order)]
for empty_row in adj_list:
empty_row.extend(int(i) for i in sys.stdin.readline().split())
# Run DFS
result = dfs(adj_list)
#result = [dfs(adj_list, n) for n in range(order)]
print(result)
arcs = count_arcs(adj_list, result)
# Print
print(arcs)
IiIiCgpCZXRoYW55IExvdwpibG93MTAwCjk2OTI5NjM2MQoKMDgvMDYvMjAyMAoKQ09NUFNDSSAyMjAgLSBBc3NpZ25tZW50IDQKUXVlc3Rpb24gMjogVHJlZSBhcmNzIGFuZCBjcm9zcyBhcmNzIGluIERGUwoKUHJvZ3JhbW1lCgo0CjEgMwoyIDMKMAoKMwoxIDIKCjEKMAoKIiIiCgojSW1wb3J0IHN5cyBhbmQgZGVxdWUgbGlicmFyeQppbXBvcnQgc3lzCmZyb20gcXVldWUgaW1wb3J0IGRlcXVlCgoKZGVmIGRmcyhhZGopOgogICAgJycnIEZ1bmN0aW9uIHRoYXQgZG9lcyBhIGRlcHRoIGZpcnN0IHNlYXJjaCBvbiBhbiBhZGphY2VuY3kgbGlzdAogICAgICAgIG9mIGEgZGlzZ3JhcGgsIHJldHVybmluZyB0aGUgcmFuayBvZiBlYWNoIG5vZGUgaW4gYSBsaXN0LiAnJycKCiAgICAjIFNldHRpbmcgdXAgcXVldWUsIGFuZCB2aXNpdGVkLCBwcmVkZWNlc3NvciBhbmQgcmFuayBhcnJheXMuCiAgICBzdGFjayA9IGRlcXVlKCkKICAgIG4gPSBsZW4oYWRqKQogICAgY29sb3VyID0gWydXaGl0ZSddKm4KICAgIHByZWQgPSBbJ051bGwnXSpuCiAgICBzZWVuID0gWy0xXSpuCiAgICBkb25lID0gWy0xXSpuCgogICAgdGltZSA9IDAKCiAgICBmb3IgaSBpbiByYW5nZSgwLG4tMSk6CiAgICAgICAgaWYgY29sb3VyW2ldID09ICdXaGl0ZSc6CiAgICAgICAgICAgIGRmc3Zpc2l0KHN0YWNrLCBhZGosIGNvbG91ciwgcHJlZCwgc2VlbiwgZG9uZSwgdGltZSwgaSkKICAgIHJldHVybiBzZWVuLCBkb25lLCBwcmVkCgpkZWYgZGZzdmlzaXQoc3RhY2ssIGFkaiwgY29sb3VyLCBwcmVkLCBzZWVuLCBkb25lLCB0aW1lLCBub2RlKToKICAgIGNvbG91cltub2RlXSA9ICdHcmV5JwogICAgc2Vlbltub2RlXSA9IHRpbWUKICAgIHRpbWUgPSB0aW1lICsgMQogICAgc3RhY2suYXBwZW5kKG5vZGUpCgogICAgd2hpbGUgbGVuKHN0YWNrKSAhPSAwOgogICAgICAgIHUgPSBzdGFja1stMV0KCiAgICAgICAgbCA9IFtpIGZvciBpIGluIGFkalt1XSBpZiBjb2xvdXJbaV09PSdXaGl0ZSddCiAgICAgICAgaWYgbGVuKGwpIT0wOgogICAgICAgICAgICBmb3IgaSBpbiBsOgogICAgICAgICAgICAgICAgY29sb3VyW2ldPSdHcmV5JwogICAgICAgICAgICAgICAgcHJlZFtpXSA9IHUKICAgICAgICAgICAgICAgIHNlZW5baV09dGltZQogICAgICAgICAgICAgICAgdGltZSA9IHRpbWUrMQogICAgICAgICAgICAgICAgc3RhY2suYXBwZW5kKGkpCiAgICAgICAgZWxzZToKICAgICAgICAgICAgc3RhY2sucG9wKCkKICAgICAgICAgICAgY29sb3VyW25vZGVdID0gJ0JsYWNrJwogICAgICAgICAgICBkb25lW25vZGVdID0gdGltZQogICAgICAgICAgICB0aW1lID0gdGltZSArIDEKCiIiIgpkZWYgcmVjdXJzaXZlREZTdmlzaXQoc3RhY2ssIGFkaiwgY29sb3VyLCBwcmVkLCBzZWVuLCBkb25lLCB0aW1lLCBub2RlKToKICAgIGNvbG91cltub2RlXSA9ICdHcmV5JwogICAgc2Vlbltub2RlXSA9IHRpbWUKICAgIHRpbWUgPSB0aW1lICsgMQoKICAgIGZvciBhZGpfbm9kZSBpbiBhZGpbbm9kZV06CiAgICAgICAgaWYgY29sb3VyW2Fkal9ub2RlXSA9PSAnV2hpdGUnOgogICAgICAgICAgICBwcmVkW2Fkal9ub2RlXSA9IG5vZGUKICAgICAgICAgICAgcmVjdXJzaXZlREZTdmlzaXQoc3RhY2ssIGFkaiwgY29sb3VyLCBwcmVkLCBzZWVuLCBkb25lLCB0aW1lLCBhZGpfbm9kZSkKICAgIAogICAgY29sb3VyW25vZGVdID0gJ0JsYWNrJwogICAgZG9uZVtub2RlXSA9IHRpbWUKICAgIHRpbWUgPSB0aW1lICsgMQoiIiIgICAgCiIiIgojIyMjIyMjIyMjCiAgICAKZGVmIGRmcyhhZGosIG5vZGUpOgoKICAgICMgU2V0dGluZyB1cCBxdWV1ZSwgYW5kIHZpc2l0ZWQsIHByZWRlY2Vzc29yIGFuZCByYW5rIGFycmF5cy4KICAgIHN0YWNrID0gZGVxdWUoKQogICAgbiA9IGxlbihhZGopCiAgICB2aXNpdGVkID0gW0ZhbHNlXSAqIGxlbihhZGopCiAgICBwcmVkX2FycmF5ID0gW05vbmVdICogbGVuKGFkaikKICAgIHNlZW4gPSBbXQogICAgZG9uZSA9IFtOb25lXSAqIGxlbihhZGopCiAgICB0aW1lID0gMAoKICAgICMgQWRkaW5nIE5vZGUgMCB0byB0aGUgcXVldWUgYW5kIHNldHRpbmcgdmlzaXRlZCBhbmQgcmFuayB2YWx1ZXMuCiAgICBzdGFjay5hcHBlbmQobm9kZSkKICAgIHZpc2l0ZWRbbm9kZV0gPSBUcnVlCiAgICBzZWVuLmFwcGVuZChub2RlKQogICAgdGltZSs9MQoKICAgICMgV2hpbGUgcXVldWUgaXMgbm90IGVtcHR5OwogICAgd2hpbGUgbGVuKHN0YWNrKSA+IDA6CiAgICAgICAgCiAgICAgICAgdSA9IHN0YWNrWy0xXSAjIFBlZWsgYXQgbGFzdCBpdGVtIC0gbm9kZSB1LgogICAgICAgIGlmIHZpc2l0ZWRbdV0gIT0gVHJ1ZToKICAgICAgICAgICAgc2Vlbi5hcHBlbmQodVswXSkKICAgICAgICAgICAgdmlzaXRlZFt3XSA9IFRydWUKICAgICAgICByZW1vdmVfZnJvbV9zdGFjayA9IFRydWUKICAgICAgICBmb3IgYWRqX25vZGUgaW4gYWRqW3VdOgogICAgICAgICAgICBpZiB2aXNpdGVkW2Fkal9ub2RlXSAhPSBUcnVlOgogICAgICAgICAgICAgICAgdmlzaXRlZFthZGpfbm9kZV0gPSBUcnVlCiAgICAgICAgICAgICAgICByZW1vdmVfZnJvbV9zdGFjayA9IEZhbHNlCiAgICAgICAgICAgICAgICBicmVhawogICAgICAgIGlmIHJlbW92ZV9mcm9tX3N0YWNrOgogICAgICAgICAgICBzdGFjay5wb3AoKQogICAgcmV0dXJuIHNlZW4KIiIiCgpkZWYgY291bnRfYXJjcyhhZGpfbGlzdCwgcmVzdWx0KToKCiAgICB0cmVlX2NvdW50ID0gMAogICAgY3Jvc3NfY291bnQgPSAwCgogICAgI3NlZW4gPSBbaSBmb3IgaiBpbiBzZWVuIGZvciBpIGluIGpdCgogICAgc2VlbiA9IHJlc3VsdFswXQogICAgZG9uZSA9IHJlc3VsdFsxXQogICAgcHJlZCA9IHJlc3VsdFsyXQogICAgCiAgICBmb3IgaW5kZXggaW4gcmFuZ2UoMCwgbGVuKGFkal9saXN0KS0xKToKICAgICAgICBpZiBhZGpfbGlzdFtpbmRleF0gIT0gW106CiAgICAgICAgICAgIHByaW50KGluZGV4KQogICAgICAgICAgICBmb3IgaiBpbiBhZGpfbGlzdFtpbmRleF06CiAgICAgICAgICAgICAgICBwcmludChqKQogICAgICAgICAgICAgICAgaWYgc2VlbltpbmRleF08c2VlbltqXTxkb25lW2luZGV4XTxkb25lW2pdOgogICAgICAgICAgICAgICAgICAgIHRyZWVfY291bnQgKz0xCiAgICAgICAgICAgICAgICAgICAgcHJpbnQoIlllcyIpCiAgICAgICAgICAgICAgICBlbGlmIHNlZW5bal08ZG9uZVtqXTxzZWVuW2luZGV4XTxkb25lW2luZGV4XToKICAgICAgICAgICAgICAgICAgICBjcm9zc19jb3VudCArPTEKICAgICAgICAgICAgICAgICAgICBwcmludCgieWVzIikKCiAgICAgICAgCiAgICByZXR1cm4oc3RyKHRyZWVfY291bnQpICsiLCIrIHN0cihjcm9zc19jb3VudCkpCgoKI01haW4gUHJvZ3JhbW1lIC0gV2hpbGUgTG9vcDsKd2hpbGUgVHJ1ZToKICAgIAogICAgIyBHZXQgdGhlIG9yZGVyIG9mIHRoZSBkaWdyYXBoLgogICAgb3JkZXIgPSBpbnQoc3lzLnN0ZGluLnJlYWRsaW5lKCkpCgogICAgIyBJZiBzeXN0ZW0gcmVhZHMgaW4gemVybywgdGhlbiBzdG9wIHByb2dyYW1tZS4KICAgIGlmIG9yZGVyID09IDA6CiAgICAgICAgYnJlYWsKICAgIAogICAgIyBSZWFkIGluIGVhY2ggYWRqYWNlbmN5IGxpc3QKICAgIGFkal9saXN0ID0gW1tdIGZvciBpIGluIHJhbmdlKG9yZGVyKV0KICAgIGZvciBlbXB0eV9yb3cgaW4gYWRqX2xpc3Q6CiAgICAgICAgZW1wdHlfcm93LmV4dGVuZChpbnQoaSkgZm9yIGkgaW4gc3lzLnN0ZGluLnJlYWRsaW5lKCkuc3BsaXQoKSkKCiAgICAjIFJ1biBERlMKICAgIHJlc3VsdCA9IGRmcyhhZGpfbGlzdCkKICAgICNyZXN1bHQgPSBbZGZzKGFkal9saXN0LCBuKSBmb3IgbiBpbiByYW5nZShvcmRlcildCiAgICBwcmludChyZXN1bHQpCiAgICBhcmNzID0gY291bnRfYXJjcyhhZGpfbGlzdCwgcmVzdWx0KQogICAgCiAgICAjIFByaW50IAogICAgcHJpbnQoYXJjcykKCg==
([0, 1, 4, 2], [7, -1, -1, -1], ['Null', 0, 1, 0])
0
1
3
1
2
3
2
0
0,0
([0, 1, 2], [5, -1, -1], ['Null', 0, 0])
0
1
2
0,0