URI PROBLEMA 1128 - Ir e Vir SOLUÇÃO EM C++

URI Online Judge | 1128

Ir e Vir

Maratona de Programação da SBC  Brasil

Timelimit: 1

Numa certa cidade há N intersecções ligadas por ruas de mão única e ruas com mão dupla de direcão. É uma cidade moderna, de forma que muitas ruas atravessam túneis ou têm viadutos. Evidentemente é necessário que se possa viajar entre quaisquer duas intersecções, isto é, dadas duas intersecções V e W, deve ser possível viajar de V para W e de W para V.

Sua tarefa é escrever um programa que leia a descrição do sistema de tráfego de uma cidade e determine se o requisito de conexidade é satisfeito ou não.

Entrada

A entrada contém vários casos de teste. A primeira linha de um caso de teste contém dois números inteiros N e M, separados por um espaço em branco, indicando respectivamente o número de intersecções (2 ≤ N ≤ 2000) e o número de ruas (2 ≤ M ≤ N(N−1)/2). O caso de teste tem ainda mais M linhas, que contêm, cada uma, uma descrição de cada uma das M ruas. A descrição consiste de três inteiros V, W e P, separados por um espaço em branco, onde V e W são identificadores distintos de intersecções (1 ≤ V, W ≤ N , V ≠ W ) e P pode ser 1 ou 2; se P = 1 então a rua é de mão única, e vai de V para W; se P = 2 então a rua é de mão dupla, liga V e W. Não existe duas ruas ligando as mesmas intersecções.

O ultimo caso de teste é seguido por uma linha que contém apenas dois números zero separados por um espaço em branco.

Saída

Para cada caso de teste seu programa deve imprimir uma linha contendo um inteiro G, onde G é igual a 1 se o requisito de conexidade está satisfeito, ou G é igual a 0, caso contrário.

#include <cstdio>

#include <vector>

#define MAX 2020

#define PB push_back

using namespace std;

typedef vector<int> vi;

int visitado[MAX],n,m;

vi grafo[MAX],transposto[MAX];

int dfs1(int u){

visitado[u]=1;

int retornar = 1;

for(vi::iterator it=grafo[u].begin();it!=grafo[u].end();it++){

int v = *it;

if (!visitado[v]){

retornar += dfs1(v);

}

}

return retornar;

}

int dfs2(int u){

visitado[u]=0;

int retornar = 1;

for(vi::iterator it=transposto[u].begin();it!=transposto[u].end();it++){

int v = *it;

if (visitado[v]){

retornar += dfs2(v);

}

}

return retornar;

}

int main(){

while(1){

scanf("%d %d",&n,&m);

if (n==0 && m == 0) break;

for(int i=1;i<=n;i++){

grafo[i].clear();

transposto[i].clear();

visitado[i]=0;

}

for(int i=0;i<m;i++){

int origem,destino,mao;

scanf("%d %d %d",&origem,&destino,&mao);

if (mao==2) {

grafo[origem].PB(destino);

transposto[destino].PB(origem);

grafo[destino].PB(origem);

transposto[origem].PB(destino);

}

else {

grafo[origem].PB(destino);

transposto[destino].PB(origem);

} 

}

if (dfs1(1)!=n) {

printf("0\n");

continue;

}

if (dfs2(1)!=n){

printf("0\n");

continue;

}

printf("1\n");

}

return 0;

}