Cod sursa(job #1245585)

Utilizator marian98Horodnic Gheorghe Marian marian98 Data 19 octombrie 2014 15:53:47
Problema Parcurgere DFS - componente conexe Scor 65
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<fstream>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,nr=0;
vector<int> noduri[100001];
vector<bool>vizitat(100001);
void adancime(int p)
{
    vizitat[p] = true;
    for (int i = 0; i < noduri[p].size(); i++) {
        if (!vizitat[noduri[p][i]]) {
            adancime(noduri[p][i]);
        }
    }
}
int main()
{
    bool gasit=1;
    ifstream d1("dfs.in");
    ofstream d2("dfs.out");
    d1>>n>>m;
    for (int i=1;i<=n;i++)
    {
        vizitat[i] = false;
        int m1, m2;
        d1>>m1>>m2;
        noduri[m1].push_back(m2);
        noduri[m2].push_back(m1);
    }
    int p=1;
    while(gasit)
    {
        gasit=0;
        for (int i=p;i<=n;i++)
            if (vizitat[i]==0)
            {
                gasit=1;
                p=i;
                break;
            }
        adancime(p);
        if (gasit) nr++;
    }
    d2<<nr;
    return 0;
}