Cod sursa(job #1661483)

Utilizator alex.vasiuVasiu Alexandru alex.vasiu Data 23 martie 2016 21:46:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
vector <int> G[100005];
int n,m;
vector <int> marcat;
void dfs(int nod,int culoare)
{
    marcat[nod]=culoare;
    for(auto p:G[nod])
        if(!marcat[p])
        dfs(p,culoare);
}
int main()
{
    f>>n>>m;
    int a,b;
    for(int i=0;i<m;i++)
    {
        f>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    marcat.resize(n+1);
    int cul=1;
    for(int i=1;i<=n;i++)
        if(!marcat[i])
    {
        dfs(i,cul);
        cul++;
    }
    g<<cul-1;

}