Cod sursa(job #2157311)

Utilizator lixiLixandru Andrei lixi Data 9 martie 2018 15:15:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include<fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int N, M, nrcomp;
bool viz[100001];
struct nod
{
    int x;
    nod *next;
};
nod *v[100001];
void add(nod *&cap, int val)
{
    nod *p = new nod;
    p->x = val;
    p->next = cap;
    cap = p;
}
void citiregraf()
{
    f >> N >> M;
    while(M--)
    {
        int x, y;
        f >> x >> y;
        add(v[x], y);
        add(v[y], x);
    }
}
void dfs(int i)
{
    viz[i] = 1;
    for(nod *p = v[i];  p != NULL; p = p->next)
        if(viz[p->x] == 0)
            dfs(p->x);
}
void comp_conexe()
{
    nrcomp = 0;
    for(int i = 1; i <= N; i++)
        if(viz[i] == 0)
        {
            nrcomp++;
            dfs(i);
        }
}
int main()
{
    citiregraf();
    comp_conexe();
    g << nrcomp;
    return 0;
}