SCC Trick

#include <iostream>

#include <vector>

#include <cstdio>

using namespace std;

#define siz 1000009

int color[siz];

int N,M;

vector <int> vec[siz];

vector <int> ans;

void dfs_visit(int n){

    color[n]=1;

    for(int i=0;i<vec[n].size();i++){

        if(color[vec[n][i]]==0){

            dfs_visit(vec[n][i]);

        }

    }

    color[n]=2;

}

void top_sort(int p){

    color[p]=1;

    for(int i=0;i<vec[p].size();i++){

        if(color[vec[p][i]]==0) top_sort(vec[p][i]);

    }

    ans.push_back(p);

    color[p]=2;

}

int main()

{

    int n,x,y;

    #ifndef ONLINE_JUDGE

    freopen("input.txt","r",stdin);

    #endif

    scanf("%d",&n);

    for(int t=0;t<n;t++){

        scanf("%d%d",&N,&M);



        //clearing vector

        for(int i=0;i<=N;i++)

            vec[i].clear();



        //pushing edges

        for(int i=0;i<M;i++){

            scanf("%d%d",&x,&y);

            vec[x].push_back(y);

        }



        //colouring

        for(int i=0;i<=N;i++)

            color[i]=0;



        //topsort

        for(int i=1;i<=N;i++)

            if(color[i]==0)top_sort(i);



        for(int i=0;i<=N;i++)

            color[i]=0;

        //dfs

        int cnt=0;

        for(int i=ans.size()-1;i>=0;i--){

            if(color[ans[i]]==0){

                cnt++;

                dfs_visit(ans[i]);

            }

        }

        printf("%d\n",cnt);

        ans.clear();

    }

    return 0;

}