Cod sursa(job #1211448)

Utilizator rangerChihai Mihai ranger Data 22 iulie 2014 16:51:11
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
typedef struct celula{
                int nod;
                celula *pred;
                } * lista;
lista gr[100010],v;
int used[100010],n,m,i,x,y,cc=0;

void df(int nod)
{
    used[nod]=1;
    lista v= new celula;
    v=gr[nod];
    while (v) {
        if (!used[v->nod]) df(v->nod);
        v=v->pred;
    }
}

int main()
{
    cin>>n>>m;
    while (m--)
        cin>>x>>y, v=new celula, v->nod=y, v->pred=gr[x], gr[x]=v,
                   v=new celula, v->nod=x, v->pred=gr[y], gr[y]=v;
    for (i=1;i<=n;i++)
        if (!used[i]) df(i),++cc;
    cout<<cc;
    return 0;
}