Pagini recente » Cod sursa (job #1270645) | Cod sursa (job #1856135) | Cod sursa (job #639836) | Cod sursa (job #2112949) | Cod sursa (job #1799251)
#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;
}