Cod sursa(job #2649857)

Utilizator Iulia25Hosu Iulia Iulia25 Data 16 septembrie 2020 17:35:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.57 kb
#include <fstream>

using namespace std;

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

int n, m, x, y, cnt;
int viz[100005];

struct nod {
int et;
nod* adr;
} *L[100005];

void dfs (int a)
{
viz[a]=1;
for(nod* nd=L[a]; nd!= NULL; nd=nd->adr)
 if(viz[nd-> et]!=1)
  dfs(nd-> et);
}
int main()  {
  int n,m;
  cin>>n>>m;
  while(cin>>x>>y)
  {
  nod* p= new nod;
  p ->et=y;
  p ->adr=L[x];
  L[x]=p;
  p= new nod;
  p ->et=x;
  p ->adr=L[y];
  L[y]=p;
  }
  for (int r = 1; r <= n; ++r)  {
    if (viz[r] == 0)  {
      ++cnt;
      dfs(r);
    }
  }
  cout << cnt;
	return 0;
}