Cod sursa(job #1509680)

Utilizator andreiblaj17Andrei Blaj andreiblaj17 Data 24 octombrie 2015 10:51:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <vector>

#define nmax 100001

using namespace std;

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

int n, m;
int firstVertex, secondVertex, numComp;
bool visited[nmax];
vector <int> G[nmax];

void read();
void solve();
void write();
void dfs();

int main()
{
    
    read();
    solve();
    write();
    
    fin.close();
    fout.close();
    
    return 0;
}

void read()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> firstVertex >> secondVertex;
        
        G[firstVertex].push_back(secondVertex);
        G[secondVertex].push_back(firstVertex);
    }
        
}

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

void solve()
{
    for (int i = 1; i <= n; i++)
        if (!visited[i])
        {
            numComp++;
            dfs(i);
        }
}


void write()
{
    fout << numComp << "\n";
}