Cod sursa(job #2199618)

Utilizator alexge50alexX AleX alexge50 Data 28 aprilie 2018 15:17:41
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <stdio.h>

const int MAX_N = 100000;
const int MAX_M = 200000;

struct Node
{
    int id;
    Node **to;
    Node *next;
};

Node* lists_pointers[MAX_N];
Node edges[MAX_M * 2];
int n_edges;

void add_edge(int x, int y)
{
    edges[n_edges].id = x;
    edges[n_edges].to = &lists_pointers[y];
    edges[n_edges].next = lists_pointers[x];

    lists_pointers[x] = &edges[n_edges];
    n_edges++;
}

char was[MAX_N];

void dfs(Node *root)
{
    if(root != NULL && was[root->id] != false)
    {
        was[root->id] = true;

        Node *x = root;
        while(x != NULL)
        {
            dfs(*(x->to));
            x = x->next;
        }
    }
}

int main()
{
    FILE *fin = fopen("dfs.in", "r"),
         *fout = fopen("dfs.out", "w");
    int n, m;
    int r;

    fscanf(fin, "%d %d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        int x, y;
        fscanf(fin, "%d %d", &x, &y);

        add_edge(x - 1, y - 1);
        add_edge(y - 1, x - 1);
    }

    r = 0;
    for(int i = 0; i < n; i++)
    {
        if(was[i] == false)
        {
            dfs(lists_pointers[i]);
            r++;
        }
    }

    fprintf(fout, "%d\n", r);

    fclose(fin);
    fclose(fout);
    return 0;
}