Cod sursa(job #1811677)

Utilizator Silviu.Stancioiu@gmail.comSilviu Stancioiu [email protected] Data 21 noiembrie 2016 14:57:47
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <stdio.h>
#include <vector>

#define MAX_N 100005
#define MAX_M 200005

using namespace std;

FILE* fin;
FILE* fout;

struct Member
{
    vector<int> neighbours;
};

int n, m;

bool used[MAX_N] = { false };

Member nodes[MAX_N];

int result = 0;

void LoadFiles()
{
    fin = fopen("dfs.in", "r");
    fout = fopen("dfs.out", "w");
}

void Init()
{
    LoadFiles();
}

void Read()
{
    int e1, e2;

    fscanf(fin, "%d %d", &n, &m);

    for(int i=0;i<m;i++)
    {
        fscanf(fin, "%d %d", &e1, &e2);

        e1--;
        e2--;

        nodes[e1].neighbours.push_back(e2);
        nodes[e2].neighbours.push_back(e1);
    }
}

void Dfs(int index)
{
    used[index] = true;

    int counts = nodes[index].neighbours.size();

    int next;

    for(int i=0;i<counts;i++)
    {
        next = nodes[index].neighbours[i];

        if(!used[next])
        {
            Dfs(next);
        }
    }
}

void Solve()
{
    for(int i=0;i<n;i++)
    {
        if(!used[i])
        {
            result++;
            Dfs(i);
        }
    }
}

void Write()
{
    fprintf(fout, "%d\n", result);
}

void CloseFiles()
{
    fclose(fin);
    fclose(fout);
}

void Terminate()
{
    CloseFiles();
}

int main(void)
{
    Init();
    Read();
    Solve();
    Write();
    Terminate();

    return 0;
}