Solução Informática Intermediário - Semana 72

Solução por Sofhia de Souza

Esse problema trata-se de um problema de Componentes Fortemente Conexas (nessa solução, iremos usar o Algoritmo de Kosaraju). É recomendado que o leitor já tenha conhecimento do algoritmo.

Trataremos o país como um grafo, e as cidades como os vértices do grafo. Analisando bem, notaremos que as cidades que são acessíveis por todas as outras cidades são aquelas que pertencem a uma mesma componente fortemente conexa (pois elas devem chegar de uma as outras), e essa componente deve ser acessada por todas as outras componentes do grafo. Em outras palavras, devemos encontrar a única componente fortemente conexa do grafo que não acessa nenhuma outra componente (caso existam mais de uma ou nenhuma, a resposta será 0). Para fazermos isso, iremos primeiro calcular as componentes fortemente conexas utilizando o algoritmo de Kosaraju, e com ele iremos guardar todos os vértices pertencentes a cada componente. Depois disso, marcaremos para cada componente se ela acessa ou não alguma outra componente (para isso, basta verificarmos os vizinhos de cada vértice e vermos se eles são ou não parte de uma mesma componente). Por fim, verificaremos se existe apenas uma componente que não aponta para nenhuma outra. Se sim, imprimimos seu tamanho e os vértices que fazem parte dela, de forma ordenada. Segue o código para melhor entendimento:

	//CAPCITY - SPOJ
	//Código por Sofhia de Souza Gonçalves

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

	const int maxn = 1e5+10;

	int n, m, vist[maxn], tempo, resp[maxn], comp[maxn]; //vist eh o vetor de visitados, tempo eh a variavel que guarda a quantidade
	//de componentes, resp eh o vetor que marca se a componente aponta ou nao pra outra,
	//e comp eh o vetor que guarda a componente de cada vertice.

	vector < int > grafo[maxn], grafo2[maxn], cont[maxn]; //grafo eh o grafo normal, grafo2 eh o grafo ao contrario e cont sao os vetores
	//dos vertices de cada componente.

	stack < int > pilha; //pilha para o algoritmo de scc

	void dfs(int u)
	{
	vist[u] = 1; //marco como visitado

	for(int v : grafo[u])
	{
	if(!vist[v]) dfs(v); //chamo pros filhos nao visitados
	}

	pilha.push(u); //coloco na pilha depois de ter passado pelos filhos
	}

	void rdfs(int u)
	{
	comp[u] = tempo; //guardo o valor da componente de u
	cont[tempo].pb(u); //adiciono u ao vetor de vertices da componente dele

	for(int v : grafo2[u])
	{
	if(!comp[v]) rdfs(v); //se os vizinhos nao foram visitados, chamo pra eles tambem
	}
	}

	void scc()
	{
	for(int i = 1 ; i <= n ; i++)
	{
	if(!vist[i]) dfs(i); //se o vertice ainda nao foi visitado, chamo a dfs
	}

	while(pilha.size()) //percorro a pilha
	{
	int u = pilha.top();
	pilha.pop();

	if(!comp[u]) //se a componente do vertice u ainda nao foi calculada, quer dizer que ele nao foi visitado ainda
	{
	tempo++; //aumento a quantidade de componentes
	rdfs(u); //chamo a dfs pro grafo contrario
	}
	}
	}

	int main()
	{
	cin >> n >> m; //leio o n e o m

	for(int i = 0 ; i < m ; i++)
	{
	int a, b;
	cin >> a >> b;
	grafo[a].pb(b); //monto o grafo
	grafo2[b].pb(a); //monto o grafo contrário
	}

	scc(); //calculo as componentes fortemente conexas

	memset(vist, 0, sizeof vist); //zero o vetor de visitados

	for(int i = 1 ; i <= n ; i++)
	{
	for(int v : grafo2[i]) //os v sao os vertices que apontam pra mim (pois estou verificando os do grafo contrario)
	{
	if(comp[i] != comp[v]) resp[comp[v]] = 1; //se a componente de i eh diferente da componente de v, quer dizer que a
	} //componente de v aponta para outra componente, entao marco resp[comp[v]] como 1
	}

	int r, c = 0;
	for(int i = 1 ; i <= tempo ; i++)
	{
	if(!resp[i]) //se a componente i nao aponta pra nenhuma outra
	{
	r = i; //guardo qual a componente
	c++; //conto a quantidade de componentes que nao apontam pra nenhuma outra componente
	}
	}

	if(c != 1) //se nenhuma componente nao aponta pra outra ou se mais de 1 componente nao aponta, a resposta eh 0
	{
	cout << "0\n";
	return 0;
	}

	cout << cont[r].size() << "\n"; //imprimo o tamanho da componente

	sort(cont[r].begin(), cont[r].end()); //ordeno os vertices da componente

	for(int i = 0 ; i < cont[r].size() ; i++)
	{
	if(i != 0) cout << " ";
	cout << cont[r][i]; // imprimo os vertices
	}
	cout << "\n";
	}

view raw

s72_intermediario.cpp

hosted with ❤ by GitHub