Montar a Árvore

dfs_capitais.cpp

#define MAXN 100100

// declaro as variáveis
int pai[MAXN], lvl[MAXN];

// declaro a lista de adjacência
vector<int> lista[MAXN];

// DFS para montar a árvore
int dfs(int v=1){ // partindo do vértice V para baixo
	
	// para cada vizinho de v
	for(int i=0; i<lista[v].size(); i++){
		
		// seja U o vizinho que estou explorando
		int u=lista[v][i];
		
		// se ele já tiver sido explorado, continuo
		if(pai[u]) continue;
		
		// caso contrário
		
		// o pai de U é V
		pai[u]=v; 
		
		// e, portanto, seu nível é o nível de V mais 1
		lvl[u]=lvl[v]+1;
		
		// e chamo a DFS em U
		dfs(u);
	}
}