Cod sursa(job #1626587)

Utilizator PetruZZatic Petru PetruZ Data 3 martie 2016 10:26:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>

using namespace std;

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

typedef struct nod{
       int inf;
       nod* next;
       }* grf;
grf a[100005];
int viz[100005],N,M;

void add(grf &n, int v){
     grf u;
     u=new nod;
     u->inf=v;
     u->next=n;
     n=u;
     }

void dfs(int n){
     grf p=a[n];
     viz[n]=1;
     while(p){
              if(!viz[p->inf]) dfs(p->inf);
              p=p->next;
              }
     }

int main() {
    
    cin >> N >> M;
    
    int x,y;
    for(int i=0; i<M; i++){
            cin >> x >> y;
            add(a[x],y);
            add(a[y],x);
            }
    int k=0;
    for(int i=1; i<=N; i++) if(!viz[i]) {dfs(i); k++;}
    cout << k;

return 0;    
}