SCC to DAG

//SCC TO DAG Convert:
#include <bits/stdc++.h>
using namespace std;
int vertex,edges;

int indegree[10005];
int low[10005];
int disc[10005];
bool taken[10005];

vector<int> Graph[10005];
vector<int> rev_Graph[10005];
vector<int> scc_List,rev_List,temp_List;
stack<int> st;
map<int,int> in_SCC,in_Boss,in_Rev,out_Graph;

int Time = 0;

void convert_SCC_To_DAG(int boss){
    rev_List.clear();
    in_SCC.clear();
    in_Boss.clear();
    in_Rev.clear();
    temp_List.clear();
    int Size = (int)scc_List.size();
    if(Size == 1) return;
    for(int i = 0;i<Size;i++){
        in_SCC[scc_List[i]] = boss;
        if(scc_List[i] != boss) out_Graph[scc_List[i]] = 1;
    }
    //Add all the neighbors of SCC members to their boss;
    for(int i = 0;i<Size;i++){
        int u = scc_List[i];
        for(int j = 0;j<(int)Graph[u].size();j++){
            int vert = Graph[u][j];
            if(in_Boss.count(vert) == 0 && in_SCC.count(vert) == 0){
                in_Boss[vert] = 1;
                temp_List.push_back(vert);
            }
        }
    }
    Graph[boss].clear();
    for(int i = 0;i<(int)temp_List.size();i++){
        Graph[boss].push_back(temp_List[i]);
    }

    //Update the nodes who have edge to SCC members.
    //Step 1: List the nodes who have edge to SCC members:
    for(int i = 0;i<Size;i++){
        int u = scc_List[i];
        for(int j = 0;j<(int)rev_Graph[u].size();j++){
            int v = rev_Graph[u][j];
            if(in_Rev.count(v) == 0 && in_SCC.count(v) == 0){
                in_Rev[v] = 1;
                rev_List.push_back(v);
            }
        }
    }

    //Step 2: Update their neighbors-remove all SCC members-add boss.
    for(int i = 0;i<(int)rev_List.size();i++){
        int u = rev_List[i];
        temp_List.clear();
        for(int j = 0;j<(int)Graph[u].size();j++){
            int vert = Graph[u][j];
            if(in_SCC.count(vert) == 0){
                temp_List.push_back(vert);
            }
        }
        Graph[u].clear();
        for(int c = 0;c<(int)temp_List.size();c++){
            Graph[u].push_back(temp_List[c]);
        }
        Graph[u].push_back(boss);
    }
}

void run_Tarjan_SCC(int u) {
    disc[u] = low[u] = ++Time;
    taken[u] = true;
    st.push(u);

    int Size = Graph[u].size();
    for (int i = 0; i < Size; i++) {
        int v = Graph[u][i];
        if (disc[v] == -1) {
            run_Tarjan_SCC(v);
            low[u] = min(low[u], low[v]);
        } else if (taken[v] == true) {
            low[u] = min(low[u], disc[v]);
        }
    }
    if (disc[u] == low[u]) {
        scc_List.clear();
        scc_List.push_back(u);
        while (st.top() != u) {
            int adj = st.top();
            taken[adj] = false;
            st.pop();
            scc_List.push_back(adj);
        }
        int adj = st.top();
        taken[adj] = false;
        st.pop();
        convert_SCC_To_DAG(u);
    }
}

void find_SCC() {
    memset(low, -1, sizeof(low));
    memset(disc, -1, sizeof(disc));
    memset(taken, false, sizeof(taken));
    Time = -1;
    for (int i = 0; i < vertex; i++) {
        if (disc[i] == -1) {
            run_Tarjan_SCC(i);
        }
    }
}

int topological_sort(){
    find_SCC();
    int cnt = 0;
    for(int u = 0;u<vertex;u++){
        if(out_Graph.count(u)  == 1) continue;
        for(int j = 0;j<(int)Graph[u].size();j++){
            int v = Graph[u][j];
            indegree[v]++;
        }
    }
    for(int u = 0;u<vertex;u++){
        if(out_Graph.count(u)  == 1) continue;
        if(indegree[u] == 0) cnt++;
    }
    return cnt;
}

void initialize() {
    out_Graph.clear();
    memset(indegree, 0, sizeof(indegree));
    for (int i = 0; i < vertex; i++) {
        Graph[i].clear();
        rev_Graph[i].clear();
    }
}

void print_Graph(){
    for(int i = 0;i<vertex;i++){
        if(out_Graph.count(i) == 1) continue;
        printf("Neighbors of %d :",i);
        int Size = (int)Graph[i].size();
        for(int j = 0;j<Size;j++){
            printf(" -> %d",Graph[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int nCase, u, v;
    scanf("%d", &nCase);
    for (int cs = 1; cs <= nCase; cs++) {
        scanf("%d %d", &vertex, &edges);
        initialize();
        for (int i = 0; i < edges; i++) {
            scanf("%d %d", &u, &v);
            u--;v--;
            if(u == v) continue;
            Graph[u].push_back(v);
            rev_Graph[v].push_back(u);
        }
        int res = topological_sort();
        printf("Case %d: %d\n",cs,res);
    }
}