Cod sursa(job #1952975)

Utilizator l-teenLucian l-teen Data 4 aprilie 2017 15:40:19
Problema Parcurgere DFS - componente conexe Scor 95
Compilator cpp Status done
Runda Arhiva educationala Marime 2.12 kb
// DFSCompConexe.cpp : Defines the entry point for the console application.
//

#include <stdio.h>

struct nodes;

struct link
{
    nodes *na, *nb;
};

struct neighbours
{
    link *l;
    neighbours *next;
};

struct nodes
{
    unsigned int conex_comp;
    neighbours *neighstart, *lastneigh;
};

bool backtrack(nodes *n, unsigned int current_cc)
{
    neighbours *neigs;
    if (n->conex_comp == -1)
    {
        n->conex_comp = current_cc;
        neigs = n->neighstart;
        while (neigs)
        {
            if (neigs->l->na == n)
                backtrack(neigs->l->nb, current_cc);
            else
                backtrack(neigs->l->na, current_cc);
            neigs = neigs->next;
        }
        return false;
    }
    else
        return true;
}

int main(int argc, char* argv[])
{
    unsigned int n, m, i, a ,b, ccs=0;
    nodes node[100000];
    neighbours neigh[400000];
    link l[200000];

    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);

    scanf("%u %u", &n, &m);

    for (i = 0; i < n; ++i)
    {
        node[i].conex_comp = -1;
        node[i].neighstart = 0;
    }
    
    for (i = 0; i < m; ++i)
    {
        scanf("%u %u", &a, &b);
        --a;
        --b;

        l[i].na = &node[a];
        l[i].nb = &node[b];

        neigh[2 * i].l = &l[i];

        if (!node[a].neighstart)
        {
            node[a].neighstart = &neigh[2*i];
            node[a].lastneigh = node[a].neighstart;
        }

        node[a].lastneigh->next = &neigh[2*i];
        node[a].lastneigh = &neigh[2*i];
        node[a].lastneigh->next = 0;

        neigh[2 * i+1].l = &l[i];

        if (!node[b].neighstart)
        {
            node[b].neighstart = &neigh[2 * i + 1];
            node[b].lastneigh = node[b].neighstart;
        }

        node[b].lastneigh->next = &neigh[2 * i + 1];
        node[b].lastneigh = &neigh[2 * i + 1];
        node[b].lastneigh->next = 0;
    }

    for (i = 0; i < n; ++i)
    {
        if (!backtrack(&node[i], ccs))
            ++ccs;
    }

    printf("%u", ccs);

	return 0;
}