Cod sursa(job #2853220)

Utilizator RobertDincaDinca Robert RobertDinca Data 20 februarie 2022 00:39:08
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include<fstream>
#include <vector>
using namespace std ;


int n,m,verif[100005];

typedef struct node
{
    int val ;
    node *next ;

} *graf;
graf v[100005];

void add(graf &dest, int num)
{
    node* nod = new node ;
    nod->val = num ;
    nod->next = dest ;
    dest = nod ;

}

void citire()
{
    ifstream f("dfs.in");


    f >> n >> m ;
    int x,y,i ;
    for(i = 0 ; i < m ; i++)
        {
            f >> x >> y ;
            add(v[x],y);
            add(v[y],x);
        }

}

void DFS(int nod)
{
    graf p;
    verif[nod] = 1 ;
    for(p = v[nod]; p != NULL ; p = p->next) if(!verif[p->val])DFS(p->val);
}

int main()
{
    citire();
    int i,cnt=0 ;
    for(i = 1; i <=n  ; i++)if(!verif[i]){cnt++;DFS(i);}
    ofstream g("dfs.out");
    g << cnt;
    g.close() ;
    return 0 ;
}