Produce the history that git log shows, from a commit graph.
What to build
A program that lists the commits reachable from HEAD, newest first, and summarizes the history.
Requirements
- Each commit has an id, a timestamp, its parent ids and a message. List every commit reachable from HEAD through parent links, sorted by timestamp from newest to oldest (ties: smaller id first), as
ID MESSAGE. - Then print
N commits, M merges, where a merge is a commit with two or more parents, andfirst-parent line: ID ID …following only first parents from HEAD.
Input
Line 1: c. Then c lines ID TIMESTAMP PARENTS MESSAGE… where PARENTS is - or ids joined by commas. Last line: the HEAD id.
Output
The history lines, then the two summary lines.
Constraints
c ≤ 500.
Example
Input:
3
a1 100 - First
b2 200 a1 Second
c3 300 b2 Third
c3
Output:
c3 Third
b2 Second
a1 First
3 commits, 0 merges
first-parent line: c3 b2 a1
Why it works
History is a graph of parent links, so a search from HEAD finds every commit that led to it, and the first-parent links trace the main line through merges.
Examples
3 a1 100 - First b2 200 a1 Second c3 300 b2 Third c3
c3 Third b2 Second a1 First 3 commits, 0 merges first-parent line: c3 b2 a1
5 a 10 - Start b 20 a Main work f 15 a Feature work m 30 b,f Merge feature x 40 a Other branch m
m Merge feature b Main work f Feature work a Start 4 commits, 1 merges first-parent line: m b a
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Collect every commit reachable from HEAD by following parent links.
Hint 2
Sort them by timestamp, newest first, breaking ties by id; the first parent is the one listed first.
Solution
Show one correct solution (try it yourself first)
commits = {}
for _ in range(int(input())):
oid, stamp, parents, message = input().split(maxsplit=3)
commits[oid] = (int(stamp), [] if parents == "-" else parents.split(","), message)
head = input().strip()
seen, stack = set(), [head]
while stack:
oid = stack.pop()
if oid not in seen:
seen.add(oid)
stack.extend(commits[oid][1])
for oid in sorted(seen, key=lambda o: (-commits[o][0], o)):
print(oid, commits[oid][2])
merges = sum(1 for o in seen if len(commits[o][1]) >= 2)
print(f"{len(seen)} commits, {merges} merges")
line, oid = [], head
while True:
line.append(oid)
if not commits[oid][1]:
break
oid = commits[oid][1][0]
print("first-parent line: " + " ".join(line))