Pagini recente » Cod sursa (job #2314680) | Cod sursa (job #2209357) | Cod sursa (job #3229753) | Cod sursa (job #2725155) | Cod sursa (job #3169929)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
const int N_MAX = 100000;
struct Nod {
bool vizitat = false;
int indexComponentConex = -1;
vector<int> indexVecini;
};
int N, M, nrComponenteConexe = 0;
Nod noduri[N_MAX];
stack<int> dfsStack;
void citire() {
fin >> N >> M;
int outNod, inNod;
for (int i = 0; i < M; i++) {
fin >> outNod >> inNod;
noduri[outNod - 1].indexVecini.push_back(inNod - 1);
noduri[inNod - 1].indexVecini.push_back(outNod - 1);
}
}
void DFS() {
while (!dfsStack.empty()) {
int parent = dfsStack.top();
dfsStack.pop();
for(int nodNou : noduri[parent].indexVecini) {
if (noduri[nodNou].vizitat) continue;
noduri[nodNou].vizitat = true;
noduri[nodNou].indexComponentConex = noduri[parent].indexComponentConex;
dfsStack.push(nodNou);
}
}
}
int main() {
citire();
for (int i = 0; i < N; i++) {
if (noduri[i].indexComponentConex != -1) continue;
noduri[i].indexComponentConex = nrComponenteConexe;
noduri[i].vizitat = true;
nrComponenteConexe++;
dfsStack.push(i);
DFS();
}
fout << nrComponenteConexe;
return 0;
}