Cod sursa(job #1221201)

Utilizator SagunistuStrimbu Alexandru Sagunistu Data 19 august 2014 20:52:40
Problema Parcurgere DFS - componente conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

struct nod
{
    int inf;
    nod *urm;
};

int n,m,nrc,s[100010];
nod *l[100010];

void citire()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        fin>>a>>b;
        nod *v;
        v=new nod;
        v->inf=b;
        v->urm=l[a];
        l[a]=v;
        v=new nod;
        v->inf=a;
        v->urm=l[b];
        l[b]=v;
    }
}

void dfs(int k)
{
    s[k]=nrc;
    for(nod *p=l[k];p;p=p->urm)
        if(s[p->inf]==0)
            dfs(p->inf);
}

int main()
{
    citire();
    nrc=0;
    for(int i=1;i<=n;i++)
        if(s[i]==0)
            nrc++,dfs(i);
    fout<<nrc;
    return 0;
}