Pagini recente » Cod sursa (job #1606302) | Cod sursa (job #235068) | Cod sursa (job #2915748) | Cod sursa (job #1671831) | Cod sursa (job #3266491)
// --------------------------------------------------------
// BFS
//#include <iostream>
//#include <fstream>
//
//#include <vector>
//#include <queue>
//
//using namespace std;
//
//
//ifstream f("bfs.in");
//ofstream g("bfs.out");
//vector<vector<int>> lista;
//queue<int> q;
//vector<int> distanta;
//
//int main()
//{
// int n,m,s;
// f >> n >> m >> s;
// int x,y ;
// lista.resize(n+1);
// distanta.resize(n+1,-1);
// q.push(s);
// distanta[s] = 0;
// while(f >> x >> y)
// {
// lista[x].push_back(y);
// }
// while(!q.empty())
// {
// int curr = q.front();
// q.pop();
// for(auto vecin : lista[curr]){
// if(distanta[vecin] == -1){
// distanta[vecin] = distanta[curr] + 1;
// q.push(vecin);
// }
// }
// }
//
// for(int i = 1; i<=n ;i++)
// g << distanta[i] << ' ' ;
//
// return 0;
//}
// -----------------------------------------------------------------------------
// DFS
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int n,m;
ifstream f("dfs.in");
ofstream g("dfs.out");
vector<vector<int>> lista;
vector<bool> verif;
void dfs(int nod)
{
if(verif[nod])return;
verif[nod] = true;
for(auto vecin: lista[nod])
{
dfs(vecin);
}
}
int main()
{
int x,y;
f >> n >> m;
lista.resize(n+1,{});
verif.resize(n+1, false);
while(f >> x >> y)
{
lista[x].push_back(y);
lista[y].push_back(x);
}
int nrComp = 0;
for(int i = 1; i<=n; i++)
{
if(!verif[i])
{
nrComp++;
dfs(i);
}
}
g << nrComp;
f.close();
g.close();
return 0;
}