Cod sursa(job #2424192)

Utilizator cochinteleandreeaCochintele Andreea Elena cochinteleandreea Data 22 mai 2019 19:24:54
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
vector<int> viz;
int n, m, s,d,nr=0;
bool ok;
vector<vector<int> > a;

void citire()
{
   int x, y, i,j;
   f >> n >>m;
   for(i=0;i<=n;i++)
    viz.push_back(0);

    vector <int> v;
    for(i=0;i<=n+1;i++)
         v.push_back(0);

   for(i=0;i<=n+1;i++)
          a.push_back(v);


   while(f>>x>>y)  a[x][y]=1;


}
void dfs(int X)
{
    viz[X] = 1;
    for(int i = 1; i <= n; i ++)
      if(a[X][i] == 1 && viz[i] == 0)
        dfs(i);
}
int main()
{
    citire();
    for( int i=1;i<=n;i++)
    {
     if(viz[i]==0) {dfs(i);nr++;}
    }
    g<<nr;
    return 0;
}