Maratona de Programação 2011

desvio.cpp

// Ivan Carvalho
// Desvio de Rua - Maratona de Programação 2011
#include <bits/stdc++.h>
#define MAXN 1001
using namespace std;
vector<int> grafo[MAXN],transposto[MAXN],bidirecional[MAXN],tipo[MAXN];
int processado[MAXN],n,m,pai[MAXN],conjuntos,iteracao,hapontes;
int dfs_low[MAXN],dfs_num[MAXN],dfs_parent[MAXN],pontosdearticulacao[MAXN],dfsNumberCounter,dfsRoot,dfsRootChildren;
int find(int x){
	if(x == pai[x]) return x;
	return pai[x] = find(pai[x]);
}
void join(int x,int y){
	x = find(x);y=find(y);
	if(x == y) return;
	if(x > y) swap(x,y);
	pai[y] = x;
	conjuntos--;
}
int dfs1(int x){
	processado[x] = iteracao;
	int retorna = 1;
	for(int i=0;i<grafo[x].size();i++){
		int v = grafo[x][i];
		if(processado[v] != iteracao) retorna += dfs1(v);
	}
	//printf("Dfs1(%d) = %d\n",x,retorna);
	return retorna;
}
int dfs2(int x){
	processado[x] = iteracao;
	int retorna = 1;
	for(int i=0;i<transposto[x].size();i++){
		int v = transposto[x][i];
		if(processado[v] != iteracao) retorna += dfs2(v);
	}
	//printf("Dfs2(%d) = %d\n",x,retorna);
	return retorna;
}
int fortemente_conexo(){
	iteracao++;
	int res1 = dfs1(1);
	//printf("\n");
	if(res1 != n) return 0;
	iteracao++;
	int res2 = dfs2(1);
	//printf("\n");
	if(res2 != n) return 0;
	return 1;
}
void dfs(int u){
	dfs_low[u] = dfs_num[u] = ++dfsNumberCounter;
	for(int i=0;i<bidirecional[u].size();i++){
		int v = bidirecional[u][i];
		if(dfs_num[v] == 0){
			dfs_parent[v] = u;
			if(u == dfsRoot) dfsRootChildren++;
			dfs(v);
			if(dfs_low[v] >= dfs_num[u]){
				pontosdearticulacao[u] = 1;
			}
			if(dfs_low[v] > dfs_num[u]){
				//printf("%d %d is bridge\n",u,v);
				//printf("%d %d\n",v,u);
				if(tipo[u][i] == 1) hapontes = 1;
			}
			dfs_low[u] = min(dfs_low[v],dfs_low[u]);
		}
		else if(v != dfs_parent[u]){
			dfs_low[u] = min(dfs_num[v],dfs_low[u]);
		}
	}
}
int main(){
	while(scanf("%d %d",&n,&m) != EOF){
		conjuntos = n;
		iteracao = 0;
		hapontes = 0;
		dfsNumberCounter = 0;
		for(int i=1;i<=n;i++){
			pai[i] = i;
			processado[i] = 0;
			grafo[i].clear();
			transposto[i].clear();
			bidirecional[i].clear();
			tipo[i].clear();
			dfs_low[i] = dfs_num[i] = dfs_parent[i] = pontosdearticulacao[i] = 0;
		}
		int u,v,ntipo;
		scanf("%d %d %d",&u,&v,&ntipo);
		for(int i=1;i<m;i++){
			scanf("%d %d %d",&u,&v,&ntipo);
			join(u,v);
			if(ntipo == 1){
				grafo[u].push_back(v);
				transposto[v].push_back(u);
			}
			else{
				grafo[u].push_back(v);
				transposto[u].push_back(v);
				grafo[v].push_back(u);
				transposto[v].push_back(u);
			}
			bidirecional[u].push_back(v);
			bidirecional[v].push_back(u);
			tipo[u].push_back(ntipo);
			tipo[v].push_back(ntipo);
		}
		if(conjuntos != 1){
			printf("*\n");
			continue;
		}
		if(fortemente_conexo()){
			printf("-\n");
			continue;
		}
		for(int i=1;i<=n;i++){
			if(dfs_num[i] == 0){
				dfsRoot = i;
				dfsRootChildren = 0;
				dfs(i);
				pontosdearticulacao[i] = (dfsRootChildren > 1);
			}
		}
		if(hapontes) printf("2\n");
		else printf("1\n");
	}
	return 0;
}