Cod sursa(job #1514287)

Utilizator mariusadamMarius Adam mariusadam Data 30 octombrie 2015 22:37:09
Problema Parcurgere DFS - componente conexe Scor 95
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
#include <vector>
#define N_MAX 1000001

using namespace std;

vector < int > G[N_MAX];
bool viz[N_MAX];

void dfs(int nod)
{
    viz[nod]=true;
    for (int i = 0; i < G[nod].size(); i++)
        if (!viz[G[nod][i]])
            dfs(G[nod][i]);
}

int main()
{
    ifstream r("dfs.in");
    ofstream w("dfs.out");
    int n,m;

    r >> n >> m;

    for (int k = 0; k < m; k++)
    {
        int i,j;
        r >> i >> j;
        G[i].push_back(j);
        G[j].push_back(i);
    }

    int nrCon=0;
    for (int i = 1; i <= n; i++)
        if (!viz[i])
        {
            nrCon++;
            dfs(i);
        }
    w << nrCon;

    r.close();
    w.close();
}