Cod sursa(job #2165796)

Utilizator HD650Stoicescu Adrian Nicolae HD650 Data 13 martie 2018 13:41:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
struct nod
{
    int val;
    nod *next;
};
nod *v[100001];
int N, M, nrc;
bool viz[100001];
void add_nod(nod *&cap, int x)
{
    nod *p = new nod;
    p->val = x;
    p->next = cap;
    cap = p;
}

void DFS(int x)
{
    viz[x] = 1;
    for(nod *p = v[x]; p != NULL; p = p->next)
        if(viz[p->val] == 0)
            DFS(p->val);
}

void comp_conexe()
{
    nrc = 0;
    for(int i = 1; i <= N; i++)
        if(viz[i] == 0)
            {
                nrc++;
                DFS(i);
            }
}

int main()
{
    int x, y;
    f >> N >> M;
    for(int i = 1; i <= M; i++)
        {
            f >> x >> y;
            add_nod(v[x], y);
            add_nod(v[y], x);
        }
    comp_conexe();
    g << nrc;
    return 0;
}