Cod sursa(job #2501971)

Utilizator rares9991Matisan Rares-Stefan rares9991 Data 30 noiembrie 2019 12:15:58
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 kb
#include <fstream>

using namespace std;

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

const int N=100001;
const int M=2*N;
int lst[N], vf[2*M], urm[2*M], n, nr,m, a, b, ct=0;
bool viz[N];


void adauga(int x, int y)
{
   vf[++nr]=y;
   urm[nr]=lst[x];
   lst[x]=nr;
}

void dfs(int x)
{
    viz[x]=true;
    ct++;
    for(int p=lst[x];p!=0;p=urm[p])
    {
       int y=vf[p];
       if(!viz[y])
       { dfs(y);}
    }
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
       fin>>a>>b;
       adauga(a,b);
    }
    int q=1, nrc=0;
    while(ct<n)
    {
       dfs(q);
       q++;
       nrc++;
    }
    fout<<nrc;
    return 0;
}