Cod sursa(job #1857107)

Utilizator radu.bRadu Brumariu radu.b Data 25 ianuarie 2017 20:20:10
Problema Parcurgere DFS - componente conexe Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 0.81 kb
#include<stdio.h>
#include<stdlib.h>

#define MAX_N 100001

struct arc *graph[MAX_N];
int visited[MAX_N];
int N, M;
int connected;

struct arc {
    int d;
    struct arc *next;
};

void dfs(int pos) {
    struct arc *p = graph[pos];
    while(p) {
        if(visited[pos]) continue;
        visited[pos] = 1;
        connected++;
        p = p->next;
    }
}

void add_node(int x, int y)
{
    struct arc *node = calloc(sizeof(struct arc), 1);
    node->d = y;
    node->next = graph[x];
    graph[x] = node;
}

int main(void)
{
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    scanf("%d %d", &N, &M);
    for(int i = 0; i < M; i++) {
        int x,y;
        scanf("%d %d", &x, &y);
        add_node(x, y);
    }
    for(int i = 1; i <= N; i++) {
        dfs(i);
    }

    printf("%d\n", connected);
}