Pagini recente » Cod sursa (job #1958471) | Cod sursa (job #241073) | Cod sursa (job #2604951) | Cod sursa (job #1351188) | Cod sursa (job #2798499)
#include <iostream>
#include <list>
#include <stack>
using namespace std;
const int nMax = 100005;
int n, m, id[nMax], low[nMax], ultId;
bool peStiva[nMax];
list<int> a[nMax];
list<list<int>> ctc;
stack<int> st;
void dfs(int x) {
st.push(x);
peStiva[x] = true;
id[x] = low[x] = ++ultId;
for (auto y: a[x]) {
// Nu am explorat nodul pana acum (neavand vreun id)
if (id[y] == 0) {
dfs(y);
}
// Am intalnit un nod care inca nu a fost atribuit unei componente conexe.
// Poate nodul curent face parte din viitoarea componenta conexa, a carei (posibila) sursa
// a fost gasita de y.
if (peStiva[y]) {
low[x] = min(low[x], low[y]);
}
}
// Am ajuns la nodul de start al ctc-ului explorat in prezent
if (id[x] == low[x]) {
list<int> compCurr;
while (true) {
auto y = st.top();
st.pop();
peStiva[y] = false;
compCurr.push_back(y);
if (y == x) break;
}
ctc.push_back(compCurr);
}
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
a[x].push_back(y);
}
// Algoritmul lui Tarjan
for (int i = 1; i <= n; i++) {
// Nu am explorat nodul pana acum (neavand vreun id)
if (id[i] == 0) {
dfs(i);
}
}
cout << ctc.size() << "\n";
for (auto &ct: ctc) {
for (auto x: ct) {
cout << x << " ";
}
cout << "\n";
}
return 0;
}