Cod sursa(job #2435008)

Utilizator Constantin.Dragancea Constantin Constantin. Data 2 iulie 2019 19:14:57
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#include <iostream>
using namespace std;

#define N 100010
int n, m, k;
bool u[N];

struct node{
    int x;
    node* nxt;
} *g[N];

void dfs(int q){
    u[q] = 1;
    for (node *r = g[q]; r; r = r->nxt)
        if (!u[r->x]) dfs(r->x);
}

int main(){
    ifstream cin ("dfs.in");
    ofstream cout ("dfs.out");
    cin >> n >> m;
    for (int i=1, x, y; i<=m; i++){
        cin >> x >> y;
        node *r, *v;
        r = new node; v = new node;
        r->x = x; v->x = y;
        r->nxt = g[y]; v->nxt = g[x];
        g[y] = r; g[x] = v;
    }
    for (int i=1; i<=n; i++)
        if (!u[i]) k++, dfs(i);
    cout << k;
    return 0;
}