Cod sursa(job #2046446)

Utilizator denismanaManaila Denis Daniel denismana Data 23 octombrie 2017 20:11:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <vector>
#include <fstream>
using namespace std;
ifstream in ("dfs.in");
ofstream out("dfs.out");
vector <unsigned> v[100002];
vector <bool> x;
unsigned n,m;
void citire()
{
    int i,a,b;
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
}
void declarare_x()
{
    int i;
    for(i=0;i<=n;i++)
        x.push_back(0);
}
void adancime(int pl)
{
    int i;
    x[pl]=1;
    for(i=0;i<v[pl].size();i++)
        if(x[v[pl][i]]==0)
            adancime(v[pl][i]);

}
int main()
{
    int y=0,i;
    citire();
    declarare_x();
    for(i=1;i<=n;i++)
    {
        if(x[i]==0)
        {
            adancime(i);
            y++;
        }
    }
    out<<y;
    return 0;

}