DFS(Depth First Search). [Input : The first line contains an integer, N(number of vertex), M(number of edge), V(start vertex number). The M line subsequent lines contains two space-separated integers, u and v, defining an connected edge between nodes u and v] [output: Print N space-separated integers the DFS path.]

DFS(Depth_First_Search).cc

#include<iostream>
#include<algorithm>
#include<stack>

using namespace std;

int graph[1001][1001]; //Graph
//N : Number of vertex
//M : Number of edge
//V : Start vertex number
int N, M, V;  

//Depth First Search
void DFS()
{
	stack<int> s;
	bool check[1001]; //Check that has passed
	int path[1000]; //Save path
	int ind = 0;
	fill(&check[0], &check[N + 1], false);

	s.push(V);
	while (!s.empty())
	{
		int now = s.top();//now : current node
		s.pop();
		if (check[now] == false)//If NOW is not passed yet
		{
			check[now] = true;//NOW has passed
			path[ind++] = now;//Insert NOW onto the path
			for (int i = N; i >= 1; i--)
			{
				if (graph[now][i] == 1 && check[i] == false)//If connection & not passed
				{
					s.push(i);//push
				}
			}
		}
	}

	//Print path
	for (int i = 0; i < ind; i++)
		cout << path[i] << " ";
	cout << endl;
}

int main()
{
	cin >> N >> M >> V;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			graph[i][j] = 0;
			graph[j][i] = 0;
		}
	}
	//Edge connection
	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		graph[a][b] = 1;
		graph[b][a] = 1;
	}
	DFS(); //Depth First Search
	return 0;
}