Cod sursa(job #1928995)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 16 martie 2017 22:30:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <vector>
#define LMAX 100005

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

vector<int> G[LMAX];
bool uz[LMAX];
int n;

void citire();
void calculare();
void dfs(int k);

int main()
{
citire();
calculare();
fin.close();
fout.close();
return 0;
}
void citire()
    {
     int i;
     int x, y;
     int m;
     fin>>n>>m;
     for (i=1;i<=m;i++)
         {
          fin>>x>>y;
          G[x].push_back(y);
          G[y].push_back(x);
         }
    }
void calculare()
    {
     int i;
     int nrc=0;
     for (i=1;i<=n;i++)
         if (!uz[i])
             {
              nrc++;
              dfs(i);
             }
     fout<<nrc<<'\n';
    }

void dfs(int k)
    {
     unsigned int i;
     uz[k]=1;
     for (i=0;i<G[k].size();i++)
          if (!uz[G[k][i]])
              dfs(G[k][i]);
    }