Cod sursa(job #1992178)

Utilizator infomaxInfomax infomax Data 19 iunie 2017 19:29:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <bitset>

using namespace std;

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

int n, m, x, y, K;
struct node{int info; node *urm;} *L[100003], *q;
bitset <100003> v;

void dfs(int nod)
{
    v[nod] = 1;
    node *p;
    p = L[nod]->urm;
    while(p != NULL)
    {
        if(!v[p->info]) dfs(p->info);
        p = p->urm;
    }
}

int main()
{
    F >> n >> m;
    for(int i = 1; i <= n; ++ i)
        L[i] = new node, L[i]->urm = NULL;
    for(int i = 0; i < m; ++ i)
    {
        F >> x >> y;
        q = new node;
        q->urm = L[x]->urm;
        q->info = y;
        L[x]->urm = q;
        q = new node;
        q->urm = L[y]->urm;
        q->info = x;
        L[y]->urm = q;
    }
    for(int i = 1; i <= n; ++ i)
        if(!v[i]) dfs(i), ++ K;
    G << K;
    return 0;
}