Answer the question git branch --contains answers.
What to build
A program that lists the branches whose history includes a given commit.
Requirements
- Commits are given with their parents; branches with their tip commits.
- For each query print
ID: BRANCH BRANCH …with the branch names sorted, orID: none.
Input
Line 1: c. Then c lines ID PARENT… (no parents for a root). Then b and b lines NAME TIP. Then q and q commit ids.
Output
q lines.
Constraints
c ≤ 1,000; b ≤ 50; q ≤ 100.
Example
Input:
4
a
b a
c b
f b
2
main c
feature f
3
a
c
f
Output:
a: feature main
c: main
f: feature
Why it works
A branch's history is everything reachable from its tip, so a commit belongs to the branches from whose tips it can be reached.
Examples
Example 1 · Input
4 a b a c b f b 2 main c feature f 3 a c f
Expected output
a: feature main c: main f: feature
Example 2 · Input
2 a x 1 main a 1 x
Expected output
x: none
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
For each branch, search from its tip through parent links and collect every reachable commit.
Hint 2
A commit is contained in a branch if it is reachable from the branch's tip, including the tip itself.
Solution
Show one correct solution (try it yourself first)
parents = {}
for _ in range(int(input())):
oid, *ps = input().split()
parents[oid] = ps
branches = dict(input().split() for _ in range(int(input())))
def reachable(tip):
seen, stack = set(), [tip]
while stack:
oid = stack.pop()
if oid not in seen:
seen.add(oid)
stack.extend(parents[oid])
return seen
history = {name: reachable(tip) for name, tip in branches.items()}
for _ in range(int(input())):
oid = input().strip()
names = sorted(name for name, seen in history.items() if oid in seen)
print(f"{oid}: " + (" ".join(names) if names else "none"))