Cod sursa(job #1455548)

Utilizator crysstyanIacob Paul Cristian crysstyan Data 28 iunie 2015 13:20:06
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#define NMAX 100001

using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

int i, n, m, ans=0, x, y;
bool viz[NMAX];

struct node
{
    int value;
    node *next;
    node ()
    {
        next = NULL;
    }
};
node *v[NMAX];

void add(node *&father, int data)
{
    node *NewNode = new node;
    NewNode -> value = data;
    NewNode -> next = father;
    father = NewNode;
}

void DFS(int i)
{
    viz[i] = 1;
    node *Node;
    for (Node = v[i]; Node != NULL; Node = Node -> next)
        if (!viz[Node -> value]) DFS(Node -> value);
}

int main()
{
    f>>n>>m;

    for (i=1; i<=m; ++i)
    {
        f>>x>>y;
        add(v[x],y);
        add(v[y],x);
    }

    for (i=1; i<=n; ++i)
        if (!viz[i])
    {
        ans++;
        DFS(i);
    }

    g<<ans<<'\n';
    return 0;
}