Cod sursa(job #2664197)

Utilizator paulm238Madaras Paul paulm238 Data 28 octombrie 2020 09:30:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int const nlim = 100001;

struct nod
{
    int a;
    nod * urm;
}*v[nlim];

void adaug( nod * & p, int x )
{
    if ( p == NULL )
    {
        p = new nod;
        p -> a = x;
        p -> urm = NULL;
    }
    else
    {
        nod * q = p;
        while(q -> urm != NULL)
            q = q -> urm;
        nod * f = new nod;
        f -> a = x;
        f -> urm = NULL;
        q -> urm = f;
    }
}

void dfs(int x, int viz[nlim])
{
    viz[x] = 1;
    while(v[x] != NULL)
    {
        if(viz[v[x]->a] == 0)
            dfs(v[x] -> a, viz);
        v[x] = v[x] -> urm;
    }
}

int cont(int viz[nlim], int n)
{
    int i, c = 0;
    for ( i = 1; i <= n ;i ++ )
    {
        viz[i] = 0;
    }
    for( i = 1; i <= n; i ++ )
    {
        if ( viz[i] == 0 )
        {
            c ++ ;
            dfs(i,viz);
        }
    }
    return c;
}

int main()
{
    int n, m, i, viz[nlim] = {0};
    in >> n >> m;
    for ( i = 1; i <= m ; i ++ )
    {
        int x, y;
        in >> x >> y;
        adaug(v[x],y);
        adaug(v[y],x);
    }
    out << cont(viz,n);
    return 0;
}