Cod sursa(job #1813440)

Utilizator jason2013Andronache Riccardo jason2013 Data 22 noiembrie 2016 22:59:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda cerculdeinfo-lectia7-grafuri Marime 0.86 kb
#include<bits/stdc++.h>
using namespace std;

#define NMax 100005

ofstream g("dfs.out");
int n, m, viz[NMax], nr;

typedef struct Node
{
    int data;
    Node* next;
} *pNode;

pNode a[NMax];

void add_edge(pNode &d, int data)
{
    pNode p = new Node;
    p->data = data;
    p->next = d;
    d = p;
}

void tip()
{
    int i, x ,y;
    ifstream f("dfs.in");

    f>>n>>m;

    for(i = 1; i <= m; i++)
    {
        f>>x>>y;
        add_edge(a[x], y);
        add_edge(a[y], x);
    }
    f.close();
}

void DFS(int nod)
{
    pNode p;
    viz[nod] = 1;
    for(p = a[nod]; p != NULL; p = p -> next)
        if(!viz[p->data])
            DFS(p -> data);
}

int main()
{
    tip();
    for(int i = 1; i <= n; i++)
        if(!viz[i])
        {
            nr++;
            DFS(i);
        }
    g<<nr;
    return 0;
}