Cod sursa(job #1235172)

Utilizator afkidStancioiu Nicu Razvan afkid Data 28 septembrie 2014 21:44:59
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstdio>
#include <vector>

using namespace std;

int n,m;

class Graph
{
    int v;
    vector<int> *adj;
    void DFSutil(int v,bool *visited);
public:
    Graph(int v);
    void addEdge(int v,int w);
    void DFS();
};

Graph::Graph(int v)
{
    this->v=v;
    adj=new vector<int>[v];
}

void Graph::addEdge(int v,int w)
{
    adj[v].push_back(w);
}

void Graph::DFSutil(int v,bool* visited)
{
    visited[v]=true;
    printf("%d ",v);
    vector<int>::iterator it;
    for(it=adj[v].begin();it!=adj[v].end();++it)
        if(!visited[*it])
            DFSutil(*it,visited);
}

void Graph::DFS()
{
    bool* visited=new bool[v];
    for(int i=1;i<v;++i)
        visited[i]=false;

    for(int i=1;i<v;++i)
        if(!visited[i])
            DFSutil(i,visited);
}


int main()
{
    int a,b;
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);

    scanf("%d %d",&n,&m);
    Graph g(n+1);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&a,&b);
        g.addEdge(a,b);
    }
    g.DFS();
    return 0;
}