Cod sursa(job #2166565)

Utilizator mrhammerCiocan Cosmin mrhammer Data 13 martie 2018 17:47:03
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<iostream>
#include<fstream>
#include<vector>
#define N_MAX 100000
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
bool viz[N_MAX];
int n,m;
int cnt;
vector< int > mat[N_MAX];
void dfs(int node)
{
    viz[node] = true;
    for(int i=0;i<mat[node].size();i++)
    {
        if(viz[mat[node][i]] == false) dfs(mat[node][i]);
    }
}
int main()
{
    cnt = 0;
    fin>>n>>m;
    int k1,k2;
    for(int i=0;i<m;i++)
    {
        fin>>k1>>k2;
        mat[k1-1].push_back(k2-1);
        mat[k2-1].push_back(k1-1);
    }
    for(int i=0;i<n;i++)
    {
        if(viz[i] == false)
        {
            cnt++;
            dfs(i);
        }
    }
    fout<<cnt;
}