Cod sursa(job #1377641)

Utilizator eneandradaEne Oana-Andrada eneandrada Data 5 martie 2015 23:18:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

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

vector <int> G[100001];
bitset <100001> viz;


/* N noduri 1<= N  <= 100 000
M muchii 0<= M <= min(200 000, N*(N+1)/2) */

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

int main()
{
    int N,M,i,a,b,nr=0;
    f>>N>>M;
    for(i=1;i<=M;i++)
    {
        f>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for(i=1;i<=N;i++)
        if(viz[i]==0)
            { nr++; DFS(i); }
    g<<nr;
    return 0;
}