Cod sursa(job #2537612)

Utilizator addamhhnAdriana Mihnea addamhhn Data 3 februarie 2020 20:02:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>

using namespace std;
ifstream fi("dfs.in");
ofstream fo("dfs.out");
struct nod{
    int x;
    nod*urm;
 };
 nod *L[100001];
 nod*p;
 int i,j,k,n,m,x,y,nc;
 int viz[100001];
void adauga(int i,int j){//pune in coada lui i(L[i]) nodul j
  nod*p;
  p=new nod;
  p->x=j;            //pune in coada lui i nodul j
  p->urm=L[i];
  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->x nevizitat
    p=p->urm;
  }
}
int main()
{
  fi>>n>>m;
  for(i=1;i<=n;i++)L[i]=0;//se fac liste vide
  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;}