Pagini recente » Cod sursa (job #3031169) | Cod sursa (job #602965) | Cod sursa (job #1124235) | Cod sursa (job #2796613)
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
class graf{
int nrN;
int nrM;
vector<vector<int>> matriceAd;
public:
graf(int n, int m, vector<vector<int>> &mat){
nrN = n;
nrM = m;
matriceAd = mat;
}
void citire()
{
for (int i = 0; i < nrM; ++i){
int x, y;
fin >> x >> y;
matriceAd[x].push_back(y);
}
}
void BFS(int S){
queue<int> coada;
int x, y;
vector<int> cost(nrN+1,-1);
cost[S] = 0;
coada.push(S);
while ( !coada.empty() ){
x = coada.front();
coada.pop();
for ( int i = 0; i < matriceAd[x].size(); ++i)
if ( cost[matriceAd[x][i]] == -1 ){
cost[matriceAd[x][i]] = cost[x] + 1;
coada.push(matriceAd[x][i]);
}
}
for ( int i = 0; i < nrN; i++ )
fout << cost[i] << " ";
}
void DFS(){
queue<int> coada;
vector<int> viz(nrN + 1, 0);
int it = 0;
for (int i = 1; i <= nrN; ++i) {
if (viz[i] == 0){
it++;
coada.push(i);
while (!coada.empty()){
int x = coada.front();
viz[x] = it;
coada.pop();
for ( int j = 1; j < matriceAd[x].size(); ++j) {
if (matriceAd[x][j] != -1 && viz[matriceAd[x][j]] == 0)
coada.push(matriceAd[x][j]);
else if (viz[matriceAd[x][j]] != 0 && viz[matriceAd[x][j]] != it) {
int itaux = viz[matriceAd[x][j]];
for (int k = 0; k < nrN; ++k) {
if (viz[k] == it)
viz[k] = itaux;
}
it--;
break;
}
}
}
}
}
fout<<it;
}
};
///BFS
//int main(){
// int n, m, S;
// fin >> n >> m >> S;
// vector<vector<int>> mat;
// vector<int> aux(1,-1);
// mat.resize(n+1, aux);
// graf G(n, m, mat);
// G.citire();
// G.BFS(S);
//
// return 0;
//}
///DFS
int main(){
int n, m;
fin>>n>>m;
vector<vector<int>> mat;
vector<int> aux(1,-1);
mat.resize(n+1, aux);
graf G(n, m, mat);
G.citire();
G.DFS();
return 0;
}