Cod sursa(job #1305985)

Utilizator alex_gabAlex Dragoi alex_gab Data 30 decembrie 2014 13:46:29
Problema Parcurgere DFS - componente conexe Scor 50
Compilator c Status done
Runda Arhiva educationala Marime 2.39 kb
#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;
}