Git: Merged and unmerged branches

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 (or merged: none), then one line NAME is N commit(s) ahead per unmerged branch, sorted by name, using commit when 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

Example 1 · Input
5
a
b a
c b
f b
g f
3
main c
feature g
old b
main
Expected output
merged: old
feature is 2 commits ahead
Example 2 · Input
2
a
b a
2
main b
done a
main
Expected output
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)

Lesson: Working with branches →