Cod sursa(job #1952724)

Utilizator l-teenLucian l-teen Data 4 aprilie 2017 12:34:55
Problema Parcurgere DFS - componente conexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
// DFSCompConexe.cpp : Defines the entry point for the console application.
//

#include <stdio.h>

struct nodes;

struct neighbours
{
    nodes *nei;
    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)
        {
            backtrack(neigs->nei, 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[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;
        
        if (a > b)
        {
            a += b;
            b = a - b;
            a = a - b;
        }

        neigh[i].nei = &node[b];

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

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

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

    printf("%u", ccs);

	return 0;
}