위상 정렬

전처리

int[] degree = new int[N+1];
ArrayList<Integer>[] G = new ArrayList[N+1];

for (int i=1; i<=N; i++)
    G[i] = new ArrayList<>();

for (int i=0; i<K; i++)
{
    st = new StringTokenizer(input.readLine());

    int u = Integer.parseInt(st.nextToken());
    int v = Integer.parseInt(st.nextToken());

    G[u].add(v);
    degree[v]++;
}

 

위상 정렬

static Queue<Integer> Topology_Sort(int N, int[] degree, ArrayList<Integer>[] G)
{
    Queue<Integer> Q = new LinkedList<>();
    Queue<Integer> Return_Q = new LinkedList<>();

    for (int i=1; i<=N; i++)
    {
        if ( degree[i] == 0 )
            Q.add(i);
    }

    while ( !Q.isEmpty() )
    {
        int u = Q.poll();
        Return_Q.add(u);

        for (int i=0; i<G[u].size(); i++)
        {
            int v = G[u].get(i);
            degree[v]--;

            if ( degree[v] == 0 )
                Q.add(v);
        }
    }

    return Return_Q;
}