UVA 11504 - Dominos Solution

Solution in C++:

///La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmanir-Rahim******///

///Abul Hasnat  Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh

///**********ALLAH IS ALMIGHTY************///

#include<bits/stdc++.h>

using namespace std;

vector<int>g[100009];

bool  v[100009];

stack<int>st;

void dfs(int s)

{

    v[s]=1;

    for(int i=0; i<g[s].size(); i++)

    {

        int x=g[s][i];

        if(v[x]==0)

            dfs(x);

    }

}

int main()

{

    int t,n,edges,nodes;

    cin>>t;

    while(t--)

    {

        cin>>n;

        memset(v,false,sizeof(v));

        cin >> edges;

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

        {

            int u, v;

            cin >> u >> v;

            g[u].push_back(v);

        }

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

        {

            if(v[i]==0)

            {

                st.push(i);

                dfs(i);

            }

        }

        memset(v,false,sizeof(v));

        int c=0;

        while(!st.empty())

        {

            int s1=st.top();

            st.pop();

            if(v[s1]==0)

            {

                c++;

                dfs(s1);

            }

        }

        cout<<c<<endl;

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

        {

            g[i].clear();

        }

    }

}