Last active
October 24, 2019 21:47
-
-
Save sofhiasouza/c2f7a24c3130a2a1e96647883a47dd97 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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