Cod sursa(job #1799251)

Utilizator nick12nicolae mihalache nick12 Data 5 noiembrie 2016 23:09:07
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>

using namespace std;

class Graph
{
    int V;    // No. of vertices
    list<int> *adj;    // Pointer to an array containing adjacency lists
    void DFSUtil(int v, bool visited[]);  // A function used by DFS
public:
    Graph(int V);   // Constructor
    void addEdge(int v, int w);   // function to add an edge to graph
    void tS();    // prints DFS traversal of the complete graph
};

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

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}

void Graph::tS()
{
    vector <int> id(V,0);
    for (int u=0;u<V;u++)
    {
        list <int>::iterator it;
        for (it = adj[u].begin(); it != adj[u].end(); it++)
            id[*it]++;
    }
    queue<int>q;
    for (int i = 0;i<V;i++)
        if (id[i] == 0)
         q.push(i);
    int cnt;
    vector <int> to;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        to.push_back(u);
        list <int>::iterator it;
        for (it = adj[u].begin(); it != adj[u].end(); it++)
            if (--id[*it] == 0)
                q.push(*it);
        cnt++;
    }
    for (int i = 0;i<to.size();i++)
        cout << to[i]+1<<" ";
}

int N,M;
int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    int i,j,k,a,b;
    scanf("%d %d",&N,&M);
    Graph g(N);
    for (i=0;i<M;i++)
    {
        scanf("%d %d",&a,&b);
        g.addEdge(a-1,b-1);
       // cout << a << b;
    }
    g.tS();

    return 0;
}