Cod sursa(job #1681513)

Utilizator DDragonXTruta Dragos Sebastian DDragonX Data 9 aprilie 2016 15:35:25
Problema Parcurgere DFS - componente conexe Scor 75
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <cstring>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

#define MAXN 50005
#define g g

int N,M;

std::vector<int> G[MAXN];

int viz[MAXN];


void dfs(int node)
{
    if (viz[node])
    {
        return;
    }
    viz[node] = 1;

    for (int i = 0; i < G[node].size(); i++)
    {
        dfs(G[node][i]);
    }
}

int main()
{
    f >> N >> M;
    for(int i=1; i<=M; i++)
    {
        int node1, node2;
        f>>node1>>node2;
        G[node1].push_back(node2);
        G[node2].push_back(node1);
    }
#if 0
    for (int i = 1; i <= N; i++)
    {
        std::cout << i << ": ";
        for (int j = 0; j < G[i].size(); j++)
        {
            std::cout << G[i][j] << ' ';
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
#endif
    int cont = 0;
    for (int i = 1; i <= N; i++)
    {
        if (viz[i] == 0)
        {
            dfs(i);
            cont++;
        }
    }
    g << cont << endl;


    return(0);
}