Cod sursa(job #1098659)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 4 februarie 2014 23:35:35
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<fstream>
using namespace std;
typedef struct celula {
           int nod;
           celula *next;
           }*lista;
lista graf[100005],v;
int n,m,i,x,y,sol;
bool viz[100005];

void dfs(int nod) {
     viz[nod]=1;
     for (lista p=graf[nod]; p; p=p->next) 
      if (viz[p->nod]==0) dfs(p->nod);
}

int main(void) {
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");
    
    fin>>n>>m;
    for (i=1; i<=m; ++i) {
         fin>>x>>y;
         v=new celula; v->nod=x; v->next=graf[y]; graf[y]=v;
         v=new celula; v->nod=y; v->next=graf[x]; graf[x]=v;
         }
    
    for (i=1; i<=n; ++i) 
     if (viz[i]==0) { ++sol; dfs(i); }
    
    fout<<sol;
 return(0);
}