Cod sursa(job #1263259)

Utilizator kiunyAndrei Gavrila kiuny Data 14 noiembrie 2014 11:49:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <vector>
#include <iostream>
#include <fstream>
#include <bitset>
using namespace std;

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

vector <vector <int> > adj;
bitset <100000> viz;
int n, m, c;

void read()
{
    f >> n >> m;
    adj.resize(n);
    viz.reset();
    int x, y;

    for(int i = 0 ; i < n; i++)
    {
        adj[i].push_back(0);
    }

    for(int i = 0; i < m; i++)
    {
        f >> x >> y;
        adj[x-1].push_back(y-1);
        adj[x-1][0]++;
        adj[y-1].push_back(x-1);
        adj[y-1][0]++;
    }
}

void DFS(int start)
{
    viz.set(start, true);
    for(int i = 1; i <= adj[start][0]; i++)
    {
        if(!viz[adj[start][i]]) DFS(adj[start][i]);
    }
}

int main()
{
    read();
    for(int i = 0; i < n; i++)
    {
        if(!viz[i])
        {
            DFS(i);
            c++;
        }
    }
    g << c;

}