Pagini recente » Cod sursa (job #2210628) | Cod sursa (job #1167841) | Statistici Crivat Mihai (Brencio) | Cod sursa (job #1061726) | Cod sursa (job #1305985)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const char *IN_FILE_NAME = "dfs.in";
const char *OUT_FILE_NAME = "dfs.out";
int adjacencyMatrix[1001][1001];
int visited[1001];
int numberOfVertices, numberOfEdges, numberOfConnectedComponents;
typedef struct stack {
int value;
struct stack *previous;
} stack;
stack *top, *next_in_stack = NULL;
void readInput();
void push(int data);
stack *pop();
void writeOutput();
int main(int argc, int *argv[]) {
readInput();
int j;
for (j = 0; j < numberOfVertices; j++) {
if (!visited[j]) {
numberOfConnectedComponents++;
push(j);
stack *nextVertex;
while ((nextVertex = pop()) != NULL) {
int value = nextVertex->value;
if (!visited[value]) {
visited[value] = 1;
int i;
for (i = numberOfVertices - 1; i >= 0; i--) {
if (adjacencyMatrix[value][i] && !visited[i]) {
push(i);
}
}
}
}
}
}
writeOutput();
return 0;
}
void readInput() {
FILE *inputFile = freopen(IN_FILE_NAME, "r", stdin);
scanf("%d %d", &numberOfVertices, &numberOfEdges);
int i, firstVertexInEdge, secondVertexInEdge;
for (i = 0; i < numberOfEdges; i++) {
scanf("%d %d", &firstVertexInEdge, &secondVertexInEdge);
adjacencyMatrix[firstVertexInEdge - 1][secondVertexInEdge - 1] = 1;
adjacencyMatrix[secondVertexInEdge - 1][firstVertexInEdge - 1] = 1;
}
fclose(inputFile);
}
void writeOutput() {
FILE *outputFile = freopen(OUT_FILE_NAME, "w", stdout);
printf("%d\n", numberOfConnectedComponents);
fclose(outputFile);
}
void push(int data) {
if (top == NULL) {
top = malloc(sizeof(stack));
memset(top, 0, sizeof(stack));
top->previous = NULL;
top->value = data;
} else {
next_in_stack = malloc(sizeof(stack));
memset(next_in_stack, 0, sizeof(stack));
next_in_stack->previous = top;
next_in_stack->value = data;
top = next_in_stack;
}
}
stack *pop() {
stack *lastElement = top;
if (lastElement != NULL) {
top = top->previous;
}
return lastElement;
}