Cod sursa(job #866578)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 28 ianuarie 2013 13:04:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

struct node
{
    int nr;
    node *next;
} *v[100001]; bool exp[100001];
int m,n,nr;

void build_graph ()
{
    int a,b;
    node *d;
    fin>>a>>b;
    d=new node;
    d->nr=a;
    d->next=v[b];
    v[b]=d;
    d=new node;
    d->nr=b;
    d->next=v[a];
    v[a]=d;
}

void DFS (int i)
{
    exp[i]=1;
    node *d=v[i];
    while (d!=NULL)
    {
        if (!exp[d->nr]) DFS (d->nr);
        d=d->next;
    }
}

int main()
{
    int i;
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        build_graph ();
    }
    for (i=1;i<=n;i++)
    {
        if (!exp[i]) {DFS(i);nr++;}
    }
    fout<<nr;
}