[SOLUTION] Count Possibilities SOLUTION CODECHEF

Problem SOLUTION CODECHEF

You are given a directed tree with $N$ vertices. The edges are directed away from the root.

For each $i = 1, 2, 3, \dots, N$ , count the number of vertices that can possibly appear at the $i$ -th position of a topological order of this tree.
That is, for each $i$ , find the number of vertices $u$ such that there exists a topological order $T$ of the graph satisfying $T_{i} = u$ .

Input Format

The first line of input will contain a single integer $T$ , denoting the number of test cases.
Each test case consists of multiple lines of input.
- The first line of each test case contains one integer $N$ .
- The next $N - 1$ lines describe the edges. The $i^{t h}$ of these $n - 1$ lines contains two space-separated integers $u_{i}$ and $v_{i}$ , denoting a directed edge from $u_{i}$ to $v_{i}$ .

Output Format

For each test case, output $N$ space-separated integers on a single line.
The $i$ -th of them should be the answer for the $i$ -th position.

Constraints

$1 \leq T \leq 3000$
$1 \leq N \leq 1 0^{5}$
$1 \leq u_{i}, v_{i} \leq N$
The input graph is a directed tree on $N$ vertices.
The sum of $N$ across all tests does not exceed $1 0^{5}$ .

Sample 1:

Input

Output

1 2 3 2
1 2 4 3 3

Explanation:

Test case $1$ : The tree is:

It has three possible topological orders:
$[1, 2, 3, 4]$
$[1, 2, 4, 3]$
$[1, 4, 2, 3]$

The counts of distinct vertices appearing at the four positions are hence $[1, 2, 3, 2]$ .

Test case $2$ : The given tree is:

Note that as a directed tree, it’s rooted at $3$ and not $1$ .

SOLUTION

from collections import defaultdict

# Function to count vertices for each position in a topological order
def count_vertices(T, edges):
# Initialize data structures to store the in-degrees, out-degrees, and counts
in_degree = defaultdict(int)
out_degree = defaultdict(int)
count = defaultdict(int)

# Populate the in-degrees and out-degrees
for u, v in edges:
out_degree[u] += 1
in_degree[v] += 1

# Initialize the queue with leaf nodes
queue = []
for u in out_degree.keys():
if out_degree[u] == 0:
queue.append(u)
count[u] = 1

# Perform a breadth-first traversal
while queue:
u = queue.pop(0)
for v in edges:
if v[0] == u:
count[v[1]] += count[u]
in_degree[v[1]] -= 1
if in_degree[v[1]] == 0:
queue.append(v[1])

return count

# Number of test cases
T = int(input())

# Iterate through each test case
for _ in range(T):
N = int(input())
edges = []
for _ in range(N – 1):
u, v = map(int, input().split())
edges.append((u, v))

# Call the function to count vertices for each position in a topological order
result = count_vertices(N, edges)

# Output the counts for each position
for i in range(1, N + 1):
print(result[i], end=” “)
print()