Pagini recente » Cod sursa (job #3187852) | Cod sursa (job #1095875) | Cod sursa (job #422465) | Cod sursa (job #1294107) | Cod sursa (job #3247653)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> v;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
void bfs(int s, int n)
{
vector<int> viz;
viz.resize(n + 2);
for(int i = 1; i <=n ; i++)
{
viz[i] = -1;
}
queue<int> coada;
coada.push(s);
viz[s] = 0;
while(!coada.empty())
{
int curent = coada.front();
coada.pop();
for(int i = 0; i < v[curent].size(); i++)
{
if(viz[v[curent][i]] == -1)
{
viz[v[curent][i]] = viz[curent] + 1;
coada.push(v[curent][i]);
}
}
}
for(int i = 1; i <= n; i++)
{
fout << viz[i] << " ";
}
}
void DFS(int s, int n, vector<int>& componenta){
for(int i = 0; i < v[s].size(); i++){
if(componenta[v[s][i]] == -1){
componenta[v[s][i]] = componenta[s];
DFS(v[s][i],n,componenta);
}
}
}
int main()
{
int n, m, s;
fin >> n >> m;
v.resize(n + 2);
for(int i = 0; i < m ; i++)
{
int x,y;
fin >> x >> y;
v[x].push_back(y);
}
vector<int> componenta;
componenta.resize(n + 1);
for(int i = 1; i <= n; i++){
componenta[i] = -1;
}
int cntr = 1;
componenta[1] = cntr;
DFS(1,n,componenta);
for(int i = 1; i <= n; i++){
if(componenta[i] == -1){
componenta[i] = ++cntr;
DFS(i,n,componenta);
}
}
fout << cntr;
}