Cod sursa(job #2740713)

Utilizator andreea.dumitrascuAndreea Dumitrascu andreea.dumitrascu Data 13 aprilie 2021 22:27:39
Problema Parcurgere DFS - componente conexe Scor 55
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <stdio.h>
#include <stdlib.h>

int n, e;

typedef struct edge {
	int leftnode;
	int rightnode;
} edge;

void dfs(int currentNode, int graphColor, edge* edges, int* visited)
{
	if (!visited[currentNode]) {
		visited[currentNode] = graphColor;
		for (int i = 1; i <= e; i++) {
			if (edges[i].leftnode == currentNode)
				dfs(edges[i].rightnode, graphColor, edges, visited);
			if (edges[i].rightnode == currentNode)
				dfs(edges[i].leftnode, graphColor, edges, visited);
		}
	}
}

int main()
{
	FILE* f = fopen("dfs.in", "r");
	fscanf(f, "%d %d", &n, &e);
	int numberGraphs = 0;
	int* visited = (int*)malloc((n + 1) * sizeof(int));
	for (int i = 1; i <= n; i++)
		visited[i] = 0;
	edge* edges = (edge*)malloc((e + 1) * sizeof(edge));
	for (int i = 1; i <= e; i++)
		fscanf(f, "%d %d", &edges[i].leftnode, &edges[i].rightnode);
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			numberGraphs++;
			dfs(i, numberGraphs, edges, visited);
		}
	}
	FILE* g = fopen("dfs.out", "w");
	fprintf(g, "%d", numberGraphs);
	fclose(f);
	fclose(g);
	/*for (int i = 1; i <= n; i++)
		printf("%d ", visited[i]);*/
}