Cod sursa(job #989401)

Utilizator gunner_292Mihai Manolescu gunner_292 Data 25 august 2013 16:21:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<fstream>
#include<vector>
#define dmax 100003

using namespace std;

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

int n, m, ccNr;

vector<int> adj[dmax];

bool visited[dmax];

void dfs(int currentN)
{
    vector<int>::iterator it;

    for(it = adj[currentN].begin(); it < adj[currentN].end(); it++)
    {
        if(visited[*it] == false)
        {
            visited[*it] = true;
            dfs(*it);
        }
    }

}


int main()
{
    in>>n>>m;

    for(int i=1; i<=m; i++)
    {
        int a, b;

        in>>a>>b;

        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    in.close();


    for(int i=1; i<=n; i++)
    {
        if(visited[i] == false)
        {
            ccNr++;
            dfs(i);
        }
    }

    out<<ccNr;

    return 0;

}