Cod sursa(job #1857114)

Utilizator radu.bRadu Brumariu radu.b Data 25 ianuarie 2017 20:27:34
Problema Parcurgere DFS - componente conexe Scor 15
Compilator c Status done
Runda Arhiva educationala Marime 0.93 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];
    visited[pos] = 1;
    while(p) {
        if(!visited[p->d])
            dfs(p->d);
        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 = 1; i <= N; i++) {
        graph[i] = NULL;
    }
    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++) {
        if(!visited[i]) {
            connected++;
            dfs(i);
        }
    }

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