Decide which branches are safe to delete, as git branch --merged does.
What to build
A program that reports which branches are merged into a target branch and how far ahead the others are.
Requirements
- Commits are given with their parents and branches with their tips. Ignore the target branch itself.
- Print
merged:followed by the merged branch names sorted (ormerged: none), then one lineNAME is N commit(s) aheadper unmerged branch, sorted by name, usingcommitwhen N is 1.
Input
Line 1: c. Then c lines ID PARENT…. Then b and b lines NAME TIP. Last line: the target branch.
Output
The merged line, then one line per unmerged branch.
Constraints
c ≤ 1,000; b ≤ 50.
Example
Input:
5
a
b a
c b
f b
g f
3
main c
feature g
old b
main
Output:
merged: old
feature is 2 commits ahead
Why it works
Everything reachable from the target is already part of it, so a branch's own work is exactly the commits reachable from its tip but not from the target's.
Examples
5 a b a c b f b g f 3 main c feature g old b main
merged: old feature is 2 commits ahead
2 a b a 2 main b done a main
merged: done
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Collect every commit reachable from the target's tip; a branch is merged if its tip is in that set.
Hint 2
For an unmerged branch, count the commits reachable from its tip that are not reachable from the target.
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())))
target = input().strip()
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
base = reachable(branches[target])
merged, ahead = [], []
for name in sorted(branches):
if name == target:
continue
if branches[name] in base:
merged.append(name)
else:
n = len(reachable(branches[name]) - base)
ahead.append(f"{name} is {n} commit{'s' if n != 1 else ''} ahead")
print("merged: " + (" ".join(merged) if merged else "none"))
for line in ahead:
print(line)