Pagini recente » Cod sursa (job #2175342) | Cod sursa (job #1637297) | Cod sursa (job #3144311) | Cod sursa (job #1270928) | Cod sursa (job #3196809)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
const int MAX_N = 100001;
std::stack<int> stiva;
std::vector<int> listaAdiacenta[MAX_N];
std::vector<std::vector<int> > tareConex;
int id[MAX_N], low[MAX_N], currentId = 1, componentaCount = 0;
// implementare algoritm Tarjan
void DFS(int current) {
id[current] = currentId;
low[current] = currentId;
currentId++;
stiva.push(current);
for (int nodVecin : listaAdiacenta[current]) {
if (id[nodVecin] == 0) {
DFS(nodVecin);
low[current] = std::min(low[current], low[nodVecin]);
} else if (stiva.size() && id[nodVecin] && low[nodVecin]) {
low[current] = std::min(low[current], id[nodVecin]);
}
}
if (id[current] == low[current]) {
std::vector<int> componenta;
int node = stiva.top();
stiva.pop();
componenta.push_back(node);
while (current != node) {
node = stiva.top();
stiva.pop();
componenta.push_back(node);
}
tareConex.push_back(componenta);
componentaCount++;
}
}
int main() {
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
int N, M, x, y;
fin >> N >> M;
for (int i = 1; i <= M; i++) {
fin >> x >> y;
listaAdiacenta[x].push_back(y);
}
for (int i = 1; i <= N; i++) {
if (id[i] == 0) {
DFS(i);
}
}
fout << componentaCount << '\n';
for (const auto &componenta : tareConex) {
for (int node : componenta) {
fout << node << " ";
}
fout << '\n';
}
return 0;
}