UVA 11504 Solution- Dominos

UVA 11504 Solution- Dominos

uva id: shoaib05
Accepted Time: 0.312
 

#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<string.h>

using namespace std;

typedef pair<int,int> Pair_Int_Int;
vector<int> edge[100010];
vector<Pair_Int_Int> answer;
set<int> myset;
bool visit[100010];
int in_time;
Pair_Int_Int p;
bool mysort(Pair_Int_Int p1, Pair_Int_Int p2)
{
    return p1.second>p2.second;
}

void topological_sort(int x)
{
    visit[x]=true;
    myset.erase(x);
    int i,y;
    for(i=0;i<edge[x].size();i++)
    {
        y=edge[x][i];
        if(visit[y]==false)
        {
            in_time++;
            topological_sort(y);
        }
    }
    p=pair<int,int>(x,++in_time);
    answer.push_back(p);
}

void dfs_result(int x)
{
    visit[x]=true;
    int i,y;
    for(i=0;i<edge[x].size();i++)
    {
        y=edge[x][i];
        if(visit[y]==false)
            dfs_result(y);
    }
}

int main() 
{
    int x,y,i,m,n,test,res;
    set<int>::iterator sit;
    cin>>test;
    while(test--)
    {
        cin>>n>>m;
        for(i=1;i<=n;i++)
        {
            edge[i].clear();
            myset.insert(i);
        }
        answer.clear();
        for(i=1;i<=m;i++)
        {
            cin>>x>>y;
            edge[x].push_back(y);
        }
        memset(visit,false,sizeof(visit));
        in_time=0;
        while(!myset.empty())
        {
            sit=myset.begin();
            x=*sit;
            in_time++;
            if(edge[x].size()==0)
            {
                visit[x]=true;
                myset.erase(x);
                p=pair<int,int>(x,++in_time);
                answer.push_back(p);
                continue;
            }
            topological_sort(x);
        }
        sort(answer.begin(),answer.end(),mysort);
        memset(visit,false,sizeof(visit));
        res=0;
        for(i=0;i<n;i++)
        {
            p=answer[i];
            if(visit[p.first]==false)
            {
                res++;
                dfs_result(p.first);
            }
        }
        cout<<res<<endl;
    }
    return 0;
}