Solução Informática Iniciante - Semana 74

Solução por Sofhia de Souza

Esse problema trata-se de um algoritmo básico de DFS. Basta contarmos a quantidade de vezes que chamamos a função e a quantidade de vezes que a retornamos, pois toda vez que chamamos a função (exceto a primeira vez), é como se Pedro fizesse um movimento indo de $x$ pra $v$ , e quando retornamos, é como se Pedro fizesse o movimento de volta de $v$ pra $x$ . Segue o código para melho entendimento:

	//Desenhando Labirintos - URI 1076
	//Sofhia de Souza Gonçalves

	#include <bits/stdc++.h>
	#define pb push_back
	using namespace std;

	const int maxn = 55;

	int t, n, v, a, vist[maxn], tempo;

	vector < int > grafo[maxn];

	int dfs(int x)
	{
	vist[x] = tempo; //marco x como visitado

	int resp = 1; //comeco com 1, pois me movimento 1 para voltar pro pai no final

	for(int v : grafo[x])
	{
	if(vist[v] == tempo) continue; //se ja visitei o vertice v nesse caso de teste, ignoro ele

	resp += dfs(v) + 1; //do contrario, chamo a dfs dele e somo na resposta da subarvore de x a resposta da subarvore de v + 1
	}

	return resp; //retorno a resposta de toda a subarvore de x
	}

	int main()
	{
	cin >> t; //leio a quantidade de casos de teste

	tempo = 1; //variavel que marca o caso de teste que estou

	while(t--)
	{
	cin >> n >> v >> a;

	for(int i = 1 ; i <= a ; i++)
	{
	int x, y;
	cin >> x >> y;

	grafo[x].pb(y); //coloco y na lista de adjacencias de x e vice-versa
	grafo[y].pb(x);
	}

	cout << dfs(n) - 1 << "\n"; //imprimo o resultado chamando a dfs, -1 pois estava contado o movimento de chegar no primeiro

	tempo++; //incremento a variavel que guarda o caso de teste, pois esse acabou

	for(int i = 0 ; i < v ; i++) grafo[i].clear(); //limpo o grafo
	}
	}

view raw

s74_iniciante.cpp

hosted with ❤ by GitHub