Cod sursa(job #2080088)

Utilizator LeVladzCiuperceanu Vlad LeVladz Data 2 decembrie 2017 13:59:08
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <vector>
#define DIM 100001

using namespace std;

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

struct nod {
    int info;
    nod *urm;
};

int p,u,i,j,x,y,v[DIM],c[DIM],S,vecin,n,m,ap;

nod *L[100001];/// vector cu 100000 de pointeri, p-urile de la fiecare lista d vecini

void dfs (int nd){
    v[nd]  = 1;
    for (nod *r = L[nd]; r!=NULL; r = r->urm)
        if (v[ r->info ] == 0)
            dfs ( r->info );
}

int main ()
{
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>x>>y;
        nod *r = new nod;
        r->info = x;
        r->urm = L[y];
        L[y] = r;

        r = new nod;
        r->info = y;
        r->urm = L[x];
        L[x] = r;
    }
    for (i=1;i<=n;i++)
        if (v[i] == 0){
            ap++;
            dfs(i);
        }
    fout<<ap;
    return 0;
}