Cod sursa(job #1820374)

Utilizator Cudrici_CarinaCudrici Carina Cudrici_Carina Data 1 decembrie 2016 17:10:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream fi("dfs.in");
ofstream fo("dfs.out");

const int MaxN = 100003;
vector<int> G[MaxN];
int n,m,sol;
bool v[MaxN];

void ReadGraph();
void Df(int x);


int main()
{
    ReadGraph();
    for(int z=1;z<=n;z++)
    if(v[z]==0) Df(z),sol++;

    fo<<sol;

}

void ReadGraph()
{
    int x, y;
    fi >> n >> m;

    while ( fi >> x >> y)
    {
        G[x].push_back(y);
        G[y].push_back(x);
    }
}




void Df(int x)
{
  v[x] = true;

  for (size_t i = 0; i < G[x].size(); ++i)
  {
      int y = G[x][i];
      if ( v[y] )
          continue;
      Df(y);
  }
}