Cod sursa(job #1827932)

Utilizator savigunFeleaga Dragos-George savigun Data 12 decembrie 2016 15:48:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
using namespace std;

struct node{
    int n;
    node *next = nullptr;
};

void add(node *n, int val){
    node *c = n;
    while(c->next != nullptr)
        c = c->next;

    node *p = new node;
    p->n = val;
    c->next = p;
}

node L[100001];
int viz[100001];


void DFS(node *p){
    viz[p -> n] = 1;

    node *c = p -> next;
    while(c != nullptr){
        if(viz[c -> n] == 0)
            DFS(&L[c -> n]);
        c = c -> next;
    }
}


int main()
{
    ifstream cin("dfs.in");
    ofstream cout("dfs.out");
    int n, m, i, x, y, s = 0;
    cin>>n>>m;

    for(i = 1; i <= n; ++i)
        L[i].n = i;

    for(i = 1; i <= m; ++i){
        cin>>x>>y;
        add(&L[x], y);
        add(&L[y], x);
    }

    for(i = 1; i <= n; ++i){
        if(viz[i] == 0){
            s++;
            DFS(&L[i]);
        }
    }

    cout<<s;

    return 0;
}