Cod sursa(job #2199626)

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

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

struct list;

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

struct list
{
    int id;
    Node *p;
}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].p;

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

char was[MAX_N];

void dfs(list *l)
{
    if(l != NULL)
    {
        Node *x = l->p;
        while(x != NULL)
        {
            /*printf("here %d\n", x->to->id);*/
            if(was[x->to->id] == false)
                /*printf("%d\n", x->to->id),*/ dfs(x->to);
            was[x->to->id] = true;
            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);
    }

    for(int i = 0; i < n; i++)
        lists_pointers[i].id = i;

    r = 0;
    for(int i = 0; i < n; i++)
    {
        if(was[i] == false)
        {
            was[i] = true;
            //printf("----\n%d\n", i);
            dfs(&lists_pointers[i]);
            r++;
        }
    }

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

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