Pagini recente » Cod sursa (job #1794525) | Cod sursa (job #1899714) | Cod sursa (job #396906) | Cod sursa (job #1992785) | Cod sursa (job #2199869)
// 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;
}