পৃষ্ঠাসমূহ

শনিবার, ১ ফেব্রুয়ারী, ২০১৪

topological sort(code)...........

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define Max 1000
#define pb push_back
#define ll long long
using namespace std;
ll indegree[Max];
vector<ll>v[Max];
vector<ll>ans;
ll topsort(ll m)
{
    ll i,j,l,k,taken[Max]={0};
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=m;j++){
        if(indegree[j]==0&&!taken[j]){
        ans.pb(j);
        taken[j]=1;
        l=v[j].size();
        for(k=0;k<l;k++)
        indegree[v[j][k]]--;
        }
        }
    }
}
int main()
{
    ll m,n,i,x,y;
    while(cin>>m>>n)
    {
        if(m==0&&n==0)
        break;
        for(i=1;i<=m;i++)
        indegree[i]=0;
        while(n--)
        {
            cin>>x>>y;
            indegree[y]++;
            v[x].pb(y);
        }
        topsort(m);
        cout<<ans[0];
        for(i=1;i<ans.size();i++)
        cout<<" "<<ans[i];
        cout<<endl;
        for(i=1;i<110;i++)
        v[i].clear();
        ans.clear();

    }

}

কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন