Cod sursa(job #1322012)

Utilizator deea101Andreea deea101 Data 19 ianuarie 2015 18:45:10
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
using namespace std;
#include <vector>
#include <stack>
#include <cstring>
#define NMAX 50001

class Graph
{

    private:
        int size; bool seen[NMAX],t[NMAX];
        vector <int> AdList[NMAX];
    public:
        vector <int> sol;

        void setSize(int n)
        {
            size=n;
			memset(seen,0,sizeof(seen));
            memset(t,0,sizeof(t));
        }
        void addEdge(int i, int j)
        {
            AdList[i].push_back(j);
            t[j]=1;
        }
        void dfs(int node)
        {
            seen[node]=1;

            for(int i=0;i<AdList[node].size();i++)
                if(!seen[AdList[node][i]])
                    dfs(AdList[node][i]);
            
            sol.push_back(node);
        }
        vector <int> toposort()
        {
            int i;
            for(i=1;i<=size;i++)
                if(!t[i])
                    dfs(i);

            int n=sol.size(),aux;
            for(i=0;i<n/2;i++)
			{
				aux=sol[i];
                sol[i]=sol[n-i-1];
				sol[n-i-1]=aux;
			}
            return sol;

        }
}G;

#include <fstream>
ifstream f("sortaret.in");
ofstream g("sortaret.out");

vector <int> v;
int main()
{
    int n,m,x,y;
    f>>n>>m;
	G.setSize(n);
    while(m--)
    {
        f>>x>>y;
        G.addEdge(x,y);
    }
    
    v=G.toposort();
    for(int i=0;i<v.size();i++)
        g<<v[i]<<' ';
}