Cod sursa(job #2199869)

Utilizator Mihai7Gheoace Mihai Mihai7 Data 29 aprilie 2018 13:59:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.1 kb
// Copyright (C) 2018 Gheoace Mihai - All Rights Reserved

#include<bitset>
#include<cstdlib>
#include <cstring>
#include <fstream>
#include <vector>
#define N 100002
#include <iostream>
std::bitset < N > viz;

std::vector<int> v[N];  // lista de vecini
int stiva[N];  // stiva de noduri care  vor fi vizitate.
int cost[N];  // distanta intre nodul x(de unde incepe bfs) si nodul i.
int grad[N][2];  // nr de vecin ai nodului
// grad intrare - grad[i][1]
//grad iesire - grad [i][0]

void DFS(int i)
{
    viz[i] = 1;
    for (std::vector<int>::iterator it = v[i].begin(); it != v[i].end(); ++it)
        if (!viz[*it])
            DFS(*it);
}
std::vector< std::string > nume;

void BFS(int rad)
{
    int l=1;

    //setam toate nodurile nevizitate.
    memset(cost, -1,sizeof(int) * N);

    stiva[l]=rad;//introduc nodul de start in coada.
    cost[rad]=0;

    for(int i = 1;i <= l; ++i)//parcurg nodurile din coada si se scot.
         for(int j = 0;j < grad[stiva[i]][0]; ++j) // Parcurg vecinii nodului ce urmeaza sa fie eliminat.
            if(cost[v[stiva[i]][j]]==-1)  // nu au fost viz.
            {//Adaug nodurile in coada si le calculez distanta.
                stiva[++l]=v[stiva[i]][j];
                cost[v[stiva[i]][j]]=cost[stiva[i]]+1;
            }

}

template <typename T>
class hashtable{
    T a;
};

int main(){
    int n, m;  // n-nr de coduri;m-nr de arce.
    int x, y, i, s;
    std::string name;  // pt citirea numelor de orase.

    // citiri.
    std::ios::sync_with_stdio(false);
    std::ifstream f("dfs.in");
    std::ofstream g("dfs.out");
    f >> n >> m ;
    /*for (i = 0; i < 3; ++i){  // citesc numele oraselor.
        f >> name;
        nume.push_back(name);
        // printf("%s ",(nume[i]).c_str());.
    }*/
    for(i=0 ; i < m; ++i){  // citeste arcele sub forma unei liste de vecini.
        f >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    int cnt = 0;
    for( i=1;i<=n;++i)
    {
        if(viz[i]==0)
        {
            ++cnt;
            DFS(i);
        }
    }
    g << cnt;
}