Skip to content

Instantly share code, notes, and snippets.

@sofhiasouza
Last active October 24, 2019 21:47
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save sofhiasouza/c2f7a24c3130a2a1e96647883a47dd97 to your computer and use it in GitHub Desktop.
Save sofhiasouza/c2f7a24c3130a2a1e96647883a47dd97 to your computer and use it in GitHub Desktop.
//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";
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment