/**
	Алгоритъм DFS
	Намира всички върхове в графа.

	parent[u] - родителят на u, по пътя до корена му в DFS.
	found[u] - за какво време е намерен връх u.
	finalized[u] - за какво време е финализиран връх u.
	
	Можем да намерим и дали в графа има цикъл:
		На реда, отбелязан със * ако colors[v] == gray и графът е ориентиран, то в него има цикъл.
		За неориентиран граф, трябва да проверим дали v e родител на u - ако да, то това не се брой за цикъл, ако не - има цикъл.
*/

#include <vector>
#include <iostream>
using namespace std;

enum color{ white, gray, black };
const int n = 9;

vector<int> graph[n] = { { 2, 3, 4, 7 }, { 2, 3, 5 }, { 0, 1, 8 }, { 0, 1, 6, 7 }, { 0, 6, 8 }, { 1, 7 }, { 3, 4 }, { 0, 3, 5 }, { 2, 4 } };

int found[n];
int finalized[n];
int parent[n];
color colors[n];
int time;

void DFS_visit(int u)
{
	colors[u] = gray;
	found[u] = ++time;

	for (int v : graph[u]) if (colors[v] == white){ parent[v] = u; DFS_visit(v); } // *

	colors[u] = black;
	finalized[u] = ++time;
}

void DFS()
{
	time = 0;
	for (int i = 0; i < n; i++){ colors[i] = white; parent[i] = -1; }
	for (int i = 0; i < n; i++)if (colors[i] == white) DFS_visit(i);
}

int main()
{
	DFS();
	
	for (int i = 0; i < n; i++)cout <<"["<< i<<": "<<found[i] << ", "<<finalized[i]<<"] ";
	cout << endl;

	return 0;
}