Pagini recente » Cod sursa (job #138243) | Cod sursa (job #1222763) | Cod sursa (job #2606478) | Cod sursa (job #1798243)
#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 DFS(); // 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::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
// cout << v << " ";
printf("%d ",v+1);
// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
if(!visited[*i])
DFSUtil(*i, visited);
}
// The function to do DFS traversal. It uses recursive DFSUtil()
void Graph::DFS()
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// Call the recursive helper function to print DFS traversal
// starting from all vertices one by one
for (int i = 0; i < V; i++)
if (visited[i] == false)
DFSUtil(i, visited);
}
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.DFS();
return 0;
}