tde_3.c

/*
* TDE 3 - Identificação de articulações, demarcadores, pontes, vértices e componentes biconexas,
* Fazer um programa que leia um arquivo de entrada arquivo.txt, contendo a descrição de vários grafos e, para cada um, liste os lowpts de cada  vértice, pontes, articulações, demarcadores, e vértices de cada componente biconexa.
*/
#include <stdio.h>
#include <string.h>
#include <locale.h>
#define TAM 10

int G[TAM][TAM];
int nivel[TAM];
int low[TAM];


int G_aux[TAM][TAM]; // acabei não usando

void mostrar_matriz(int matriz[TAM][TAM]){
	// número coluna
	printf("\n");
	printf("X ");
	for(int i=1; i<TAM+1; i++){
		printf("%d ", i);
	}
	printf("\n");
	// iterar
	for(int i=0; i<TAM; i++){
		printf("%d ", i+1); // número linha
		for(int j=0; j<TAM; j++){
			printf("%d ", matriz[i][j]); // valor
		}
		printf("\n");
	}
	printf("\n");
}

void inserir_aresta(int vi, int vf){
	G[vi-1][vf-1] = 1;
	G[vf-1][vi-1] = 1; // não-direcionada
	return;
}

void dfs_basica(int v, int niv, int N, int articulacoes[TAM]){
	nivel[v]=niv;
	int i;
	if(articulacoes[v]){
		return;
	}
	for (i=0;i<N;i++){
		if (G_aux[v][i]==2 && nivel[i]==-1)
		{
			printf("%d ", i+1);
			dfs_basica(i,niv+1, N, articulacoes);
		}
	}
}

int dfs(int v, int niv, int pai, int N)
{
	nivel[v]=niv;
	int i;
	for (i=0;i<N;i++){
		if (G[v][i]==1 && nivel[i]==-1)
		{
			G[v][i]=2;
			G[i][v]=0;
			dfs(i,niv+1,v, N);
		}
	}
}



int lowpt(int v, int N)
{
	if (low[v]!=-1)
		return low[v]; // se low[v] já está definido, retorna
	low[v]=v; // valor inicial é o próprio v
	int i;
	for (i=0;i<N;i++){
		if (G[v][i]==2 && nivel[lowpt(i,N)]<nivel[low[v]]){
			low[v]=low[i]; // se lowpt do filho é menor, atualiza lowpt do pai
		} else if (G[v][i]==1 && nivel[i]<nivel[low[v]]){
			low[v]=i; // se tem aresta de retorno para cima, atualiza lowpt
		}
	}
	return low[v];
}

int main(){
	int grafos, n, m, vi, vf, flag;
	grafos= 0; n = 0; m = 0; vi =0; vf = 0; flag = 0;
	setlocale(LC_ALL, "Portuguese");
	
	
	// arquivo:
	FILE *arqgrafo = fopen("grafo.txt", "rt");
	
	// leitura número grafos, vértices, arestas:
	fscanf(arqgrafo, "%d", &grafos);
	while(grafos){
		//limpeza
		memset(G, 0, sizeof(int) * TAM * TAM);
		memset(nivel, -1, sizeof(int) * TAM);
		memset(low, -1, sizeof(int) * TAM);
		
		fscanf(arqgrafo, "%d", &n); // número vértices
		fscanf(arqgrafo, "%d", &m); // número arestas
		
		while(m > 0){
			fscanf(arqgrafo, "%d", &vi);
			fscanf(arqgrafo, "%d", &vf);
			inserir_aresta(vi, vf);
			m--;
		}
		
		dfs(0, 0, -1, n);
		
		int low_num;
		printf("Lowpts: ");
		for(int i=0; i<n; i++){
			low_num = lowpt(i, n)+1;
			printf("%d:%d ", i+1, low_num);
		}
		printf("\n");
		
		printf("Pontes: ");
		flag = 1;
		for(int i=0; i<n; i++){
			low_num = lowpt(i, n)+1;
			if(i!=0 && i+1==low_num){
				for(int j=0;j<n;j++){
					if(G[j][i+1]){
						flag = 0;
						printf("(%d, %d) ", j, i+1);
					}
				}
				printf("\n");
			}
		}
		if(flag)
			printf("nenhuma\n");
		
		printf("Articulações: ");
		int articulacoes[TAM] = {0};
		int demarcadores[TAM] = {0};
		memset(demarcadores, -1, sizeof(int) * TAM);
		// se é raíz de t (vértice 1) e possui mais de um filho .. é articulação:
		int count = 0;
		for(int j=1; j<n; j++){
			if(G[0][j] == 2){
				count++;
				demarcadores[j] = 0;
				//printf("* %d é demarcador da raíz *\n", j+1); //
			}
			if(count>1){
				articulacoes[0] = 1;
			}
		}
		
		// se não é raíz de t ..... e tem um filho (w) .. que o valor do lowpt dele é v .. ou w ... é articulação:
		for(int i=1; i<n; i++){
			// para cada filho:
			for(int j=0; j<n; j++){
				if(G[i][j] == 2)
					if((lowpt(j, n)+1 == i+1)  ||  (lowpt(j, n)+1 == j+1)){
						demarcadores[j] = i;
						articulacoes[i] = 1;
						//printf("* %d é demarcador de %d *\n", j+1, i+1);
						break;
					}
			}
		}
		
		flag = 1;
		for(int i=0; i<n; i++)
			if(articulacoes[i]){
				printf("%d ", i+1);
				flag = 0;
			}
		if(flag)
			printf("nenhuma");
		
		printf("\n");
		
		printf("Demarcadores: ");
		for(int i=0; i<n; i++)
			if(demarcadores[i] >= 0)
				printf("%d ", i+1);
		printf("\n");
		
		
		printf("\nComponentes biconexas: \n");
		for(int i=0; i<n; i++){
			if(demarcadores[i] >= 0){
				printf("%d %d ", demarcadores[i]+1, i+1);
				memset(nivel, -1, sizeof(int) * TAM);
				memcpy(G_aux, G, sizeof(int) * TAM * TAM); // cópia da matriz para remover arestas do grafo .. sem alterar o original ... acabei nem precisando
				dfs_basica(i, 0, n, articulacoes); // também vai mostrar vértices lá de dentro do DFS
				printf("\n");
			}
		}
		printf("\n");
		grafos--;
		if(grafos)
			printf("--------------------------------\n");
	}
	return 0;
}

/* 4 vértices e 6 arestas, 0 (zero) pontes e articulações
1
4 6
1 2
1 3
1 4
2 3
2 4
3 4
*/


/* 6 vértices, 7 arestas, 1 ponte
1
6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6
*/

grafo.txt

2

6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6

4 6
1 2
1 3
1 4
2 3
2 4
3 4