Cod sursa(job #1242737)

Utilizator LycrsTrifan Tamara Lycrs Data 14 octombrie 2014 22:36:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#include <algorithm>
using namespace std;

ifstream cin("dfs.in");
ofstream cout("dfs.out");

typedef struct ls
{
    int info;
    ls *next;
} *nod;

int x, y, i, j, k, m, n, r=0;
nod a[100005];
bool viz[100005];

void ad(int x, nod &y)
{
    nod p=new ls;
    p->info=x;
    p->next=y;
    y=p;
}

void dfs(int x)
{
    nod p=new ls;
    p=a[x];
    viz[x]=1;
    for (p=p; p; p=p->next)
        if (viz[p->info]==0) dfs(p->info);
}



int main()
{
    cin>>n>>m;
    for (i=1; i<=m; ++i)
    {
        cin>>x>>y;
        ad(x, a[y]);
        ad(y, a[x]);
    }

    for (i=1; i<=n; ++i)
        if (viz[i]==0)
    {
        ++r;
        dfs(i);
    }


    cout<<r;
    return 0;
}