Cod sursa(job #1161954)

Utilizator Mihai_ChihaiMihai Chihai Mihai_Chihai Data 31 martie 2014 15:48:48
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
using namespace std;


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

typedef struct celula{
            int nod;
            celula *pred;
            } *lista;
lista graf[10000],v;
int viz[100000],n,m,i,j,x,y,sol;
void dsf(int nod)
{
    viz[nod]=1;
    for (lista p=graf[nod];p;p=p->pred)
        if (!viz[p->nod]) dsf(p->nod);
}

int main()
{
    fin>>n>>m;
    int i;
    for (i=1;i<=m;i++) {
            int x,y;
            fin>>x>>y;
            v= new celula; v->nod=y; v->pred=graf[x]; graf[x]=v;
            v= new celula; v->nod=x; v->pred=graf[y]; graf[y]=v;
    }

    int ans=0;
    for (i=1;i<=n;i++)
        if (!viz[i]) { dsf(i); ans++;};
    fout<<ans;
      fin.close();
      fout.close();
}