Cod sursa(job #1226520)

Utilizator vevuiocsaIocsa Valeriu Ionut vevuiocsa Data 5 septembrie 2014 21:08:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>

using namespace std;

struct Edge
{
    int v;
    Edge *next;
};

struct List
{
    Edge *begin;

    List()
    {
        begin = NULL;
    }

    void Insert(int v)
    {
        if (begin == NULL)
        {
            begin = new Edge;
            begin->v = v;
            begin->next = NULL;
        }
        else
        {
            Edge *aux = new Edge;
            aux->v = v;
            aux->next = begin;
            begin = aux;
        }
    }
};

List Graph[100001];
int N, M;
bool Visited[100001];

void Parcurgere(int node)
{
    Visited[node] = true;
    for (Edge *e = Graph[node].begin; e != NULL; e = e->next)
        if (!Visited[e->v])
            Parcurgere(e->v);
}

int main()
{
    ifstream fin("dfs.in");
    fin >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        int a, b;
        fin >> a >> b;
        Graph[a].Insert(b);
        Graph[b].Insert(a);
    }
    fin.close();
    for (int i = 1; i <= N; i++)
        Visited[i] = false;
    int connectedComponentCount = 0;
    for (int i = 1; i <= N; i++)
    {
        if (!Visited[i])
        {
            connectedComponentCount++;
            Parcurgere(i);
        }
    }
    ofstream fout("dfs.out");
    fout << connectedComponentCount;
    fout.close();
    return 0;
}