Cod sursa(job #2535746)

Utilizator MaraValeanMara Valean MaraValean Data 1 februarie 2020 11:07:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
#define M 100001

using namespace std;
ifstream fi("dfs.in");
ofstream fo ("dfs.out");
struct nod{
int x;
nod *urm;};
nod*L[M];
nod* p;
int i,j,k,n,m,x,y,nc,viz[M];
void adauga (int i, int j)
{ nod *p;
  p=new nod;
  p->urm=L[i];
  p->x=j;
  L[i]=p;

}
void DFS(int j){
nod *p;
viz[j]=1;
p=L[j];
while(p){                      //se merge pe vecinii nodului j
    if(viz[p->x]==0)DFS(p->x);
    p=p->urm;
  }
}
int main()
{ fi>>n>>m;
  for(i=1;i<=n;i++)
    L[i]=0;
  for(i=1;i<=m;i++)
  { fi>>x>>y;
    adauga(x,y);
    adauga(y,x);
  }
  for(i=1;i<=n;i++)
    if(viz[i]==0)
  {
      nc++;
      DFS(i);
  }
  fo<<nc;
    return 0;
}