from collections import deque

def topological_sort_bfs(n, graph):
    indegree = [0] * n

    # Calculate indegree
    for i in range(n):
        for node in graph[i]:
            indegree[node] += 1

    print(indegree)

    q = deque()
    ans = []

    # Push nodes with indegree 0
    for i in range(n):
        if indegree[i] == 0:
            q.append(i)

    while q:
        curr = q.popleft()
        ans.append(curr)

        for neighbor in graph[curr]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                q.append(neighbor)

    if len(ans) != n:
        print("Graph has a cycle, and topo sort is not possible.")
        return []

    return ans


n = 6
adj = [
    [],
    [],
    [3],
    [1],
    [0, 1],
    [0, 2]
]

print(topological_sort_bfs(n, adj))
    

import java.util.*;

class Solution {
    static List topologicalSortBFS(int n, List> graph) {
        int[] indegree = new int[n];

        // Calculate indegree
        for (int i = 0; i < n; i++) {
            for (int node : graph.get(i)) {
                indegree[node]++;
            }
        }

        System.out.println(Arrays.toString(indegree));

        Queue q = new LinkedList<>();
        List ans = new ArrayList<>();

        // Add nodes with indegree 0
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                q.add(i);
            }
        }

        while (!q.isEmpty()) {
            int curr = q.poll();
            ans.add(curr);

            for (int neighbor : graph.get(curr)) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    q.add(neighbor);
                }
            }
        }

        if (ans.size() != n) {
            System.out.println("Graph has a cycle, and topo sort is not possible.");
            return new ArrayList<>();
        }

        return ans;
    }

    public static void main(String[] args) {
        int n = 6;
        List> graph = new ArrayList<>();

        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

        graph.get(2).add(3);
        graph.get(3).add(1);
        graph.get(4).add(0);
        graph.get(4).add(1);
        graph.get(5).add(0);
        graph.get(5).add(2);

        System.out.println(topologicalSortBFS(n, graph));
    }
}
  

#include <bits/stdc++.h>
using namespace std;

vector topologicalSortBFS(int n, vector>& graph) {
    vector indegree(n, 0);

    for (int i = 0; i < n; i++) {
        for (int node : graph[i]) {
            indegree[node]++;
        }
    }

    for (int x : indegree) cout << x << " ";
    cout << endl;

    queue q;
    vector ans;

    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        ans.push_back(curr);

        for (int neighbor : graph[curr]) {
            indegree[neighbor]--;
            if (indegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }

    if (ans.size() != n) {
        cout << "Graph has a cycle, and topo sort is not possible." << endl;
        return {};
    }

    return ans;
}

int main() {
    int n = 6;
    vector> graph(n);

    graph[2].push_back(3);
    graph[3].push_back(1);
    graph[4].push_back(0);
    graph[4].push_back(1);
    graph[5].push_back(0);
    graph[5].push_back(2);

    vector res = topologicalSortBFS(n, graph);
    for (int x : res) cout << x << " ";
}

#include <stdio.h>

int graph[6][2] = {
    {},
    {},
    {3},
    {1},
    {0, 1},
    {0, 2}
};

int size[] = {0, 0, 1, 1, 2, 2};

int main() {
    int n = 6;
    int indegree[6] = {0};

    // Calculate indegree
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < size[i]; j++) {
            indegree[graph[i][j]]++;
        }
    }

    for (int i = 0; i < n; i++)
        printf("%d ", indegree[i]);
    printf("\n");

    int queue[6], front = 0, rear = 0;
    int ans[6], idx = 0;

    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            queue[rear++] = i;
        }
    }

    while (front < rear) {
        int curr = queue[front++];
        ans[idx++] = curr;

        for (int j = 0; j < size[curr]; j++) {
            int neighbor = graph[curr][j];
            indegree[neighbor]--;
            if (indegree[neighbor] == 0) {
                queue[rear++] = neighbor;
            }
        }
    }

    if (idx != n) {
        printf("Graph has a cycle, and topo sort is not possible.\n");
        return 0;
    }

    for (int i = 0; i < n; i++)
        printf("%d ", ans[i]);

    return 0;
}

using System;
using System.Collections.Generic;

class Solution {
    static List TopologicalSortBFS(int n, List[] graph) {
        int[] indegree = new int[n];

        for (int i = 0; i < n; i++) {
            foreach (int node in graph[i]) {
                indegree[node]++;
            }
        }

        Console.WriteLine(string.Join(" ", indegree));

        Queue q = new Queue();
        List ans = new List();

        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                q.Enqueue(i);
            }
        }

        while (q.Count > 0) {
            int curr = q.Dequeue();
            ans.Add(curr);

            foreach (int neighbor in graph[curr]) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    q.Enqueue(neighbor);
                }
            }
        }

        if (ans.Count != n) {
            Console.WriteLine("Graph has a cycle, and topo sort is not possible.");
            return new List();
        }

        return ans;
    }

    static void Main() {
        int n = 6;
        List[] graph = new List[n];

        for (int i = 0; i < n; i++)
            graph[i] = new List();

        graph[2].Add(3);
        graph[3].Add(1);
        graph[4].Add(0);
        graph[4].Add(1);
        graph[5].Add(0);
        graph[5].Add(2);

        var result = TopologicalSortBFS(n, graph);
        Console.WriteLine(string.Join(" ", result));
    }
}