Cod sursa(job #2388427)

Utilizator susanuradu1999Susan Radu susanuradu1999 Data 26 martie 2019 01:48:25
Problema Parcurgere DFS - componente conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

vector <int> a[100001];
int v[100001],k=1,n,c[100001];

void DFS(int x)
{
 int vecin;
  while(!a[x].empty())
     {
      if(v[a[x].back()]==0)
      {
       vecin=a[x].back();
       k++;
       c[k]=vecin;
       v[vecin]=1;
       DFS(vecin);
       a[x].pop_back();
      }
       else a[x].pop_back();
     }
}

int main()
{
  int m,i,j,z,y,comp_conex=0;
  fin>>n>>m;

  for(i=1;i<=m;i++)
   {
    fin>>z>>y;
    a[z].push_back(y);
    a[y].push_back(z);
   }

  for(i=1;i<=n;i++)
  {

   if(v[i]==0)
  {
   comp_conex++;

   c[1]=i;
   v[i]=1;

   DFS(i);

   for(j=1;j<=n;j++)
       c[j]=0;
  }
  }

  fout<<comp_conex;

 return 0;
}