# [SOLUTION] Count Possibilities SOLUTION CODECHEF

## Problem SOLUTION CODECHEF

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

For each �=1,2,3,…,�, count the number of vertices that can possibly appear at the -th position of a topological order of this tree.
That is, for each , find the number of vertices  such that there exists a topological order  of the graph satisfying ��=�.

### Input Format

• The first line of input will contain a single integer , 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 .
• The next �−1 lines describe the edges. The ��ℎ of these �−1 lines contains two space-separated integers �� and ��, denoting a directed edge from �� to ��.

### Output Format

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

### Constraints

• 1≤�≤3000
• 1≤�≤105
• 1≤��,��≤�
• The input graph is a directed tree on  vertices.
• The sum of  across all tests does not exceed 105.

### Sample 1:

Input

Output

2
4
1 2
2 3
1 4
5
3 1
3 2
1 5
1 4

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

while queue:
u = queue.pop(0)
for v in edges:
if v == u:
count[v] += count[u]
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)

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()