Cod sursa(job #2241610)

Utilizator AnDrEeA1915Monea Andreea AnDrEeA1915 Data 16 septembrie 2018 14:30:29
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
int n, m, viz[100001], nr = 0;

typedef struct N
{
    int from;
    N *to;
}*Node;
Node l[100001];

void inserare(Node &dest, int val)
{
    Node p = new N;
    p -> from = val;
    p -> to = dest;
    dest = p;
}

void DFS(int node)
{
    Node p;
    viz[node] = 1;
    for (p = l[node]; p != NULL; p = p -> to)
        if(!viz[p -> from])
            DFS(p -> from);

}
int main()
{
    fin >> n >> m;
    for (int i = 0; i < m ; ++i)
    {
        int x, y;
        fin >> x >> y;
        inserare(l[x], y);
        inserare(l[y], x);
    }
    for (int i = 0; i < n; ++i)
         if(!viz[i])
         {
            nr++;
            DFS(i);
         }
    fout << nr << endl;
    return 0;
}