Monday, December 19, 2016

Easy topological sort problem in C++. UVa-10305

Please don't copy code.At first try to understand the topological sort algorithm.
Best explanation in Bangla Language টপোলজিকাল সর্ট.


Implementation in C++.

Source code:

#include<bits/stdc++.h>
using namespace std;
int result[101];
vector<int>ans;
int main()
{
    vector<int>G[101];

    int n,m;
    while(cin>>n>>m)
    {
        if(n==0 && m==0)
            break;
        ans.clear();
        memset(result,0,sizeof result);
        for(int i=0; i<m; i++)
        {
            int node1,node2;
            cin>>node1>>node2;
            G[node1].push_back(node2);
            result[node2]++;
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(result[j]==0)
                {
                    for(int k=0; k<G[j].size(); k++)
                    {
                        int t = G[j][k];
                        result[t]--;
                    }
                    result[j]=-1;
                    ans.push_back(j);
                    break;
                }
            }

        }
        for(int i=0; i<n; i++)
        {
            cout<<ans[i];
            if(i!=n-1)
                cout<<" ";
        }
        cout<<endl;

        for(int i=0;i<=n;i++)
        {
            G[i].clear();
        }

    }
    return 0;
}

No comments:

Post a Comment