Cod sursa(job #1954222)

Utilizator l-teenLucian l-teen Data 5 aprilie 2017 11:49:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
// DFSCompConexe.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
#include <string.h>

struct link *nodes;

struct link
{
    unsigned int v;
    link *next;
};

void backtrack(link *node)
{
    if (!node->v)
    {
        node->v = -1;
        link *p = node->next;
        while (p)
        {
            backtrack(&nodes[p->v]);
            p = p->next;
        }
    }
}

void read(link *node, unsigned int m, const unsigned int n)
{
    unsigned int i, a, b;
    struct link *p[100000], *new_link;

    for (i = 0; i < n; ++i)
    {
        p[i] = node + i;
    }

    for (i = 0; i < m; ++i)
    {
        scanf("%u %u", &a, &b);
        --a;
        --b;
        new_link = new link;
        new_link->v = b;
        new_link->next = 0;
        p[a]->next = new_link;
        p[a] = new_link;

        new_link = new link;
        new_link->v = a;
        new_link->next = 0;
        p[b]->next = new_link;
        p[b] = new_link;
    }
}


int main(int argc, char* argv[])
{
    unsigned int n, m, i, cc = 0;

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

    scanf("%u %u", &n, &m);
    nodes = new link[n];

    memset(nodes, 0x00, sizeof(*nodes)*n);

    read(nodes, m, n);
    for (i = 0; i < n; ++i)
        if (!nodes[i].v)
        {
            backtrack(&nodes[i]);
            ++cc;
        }

    printf("%u", cc);

	return 0;
}