Cod sursa(job #2199615)

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

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

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

Node* lists_pointers[MAX_N];
Node connections[MAX_M * 2];

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(lists_pointers[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);
        x --;
        y --;

        connections[2 * i] = {x, y, lists_pointers[y]};
        connections[2 * i + 1] = {y, x, lists_pointers[x]};

        lists_pointers[y] = &connections[2 * i];
        lists_pointers[x] = &connections[2 * i + 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;
}