Pagini recente » Cod sursa (job #2151580) | Cod sursa (job #346923) | Cod sursa (job #779329) | Cod sursa (job #649137) | Cod sursa (job #2897442)
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector <int> M[100005], aux;
vector <vector<int>> sol;
int idx[100005], lowlink[100005], desc;
bool in_stack[100005];
stack <int> st;
void tarjan(int n)
{
idx[n] = lowlink[n] = ++desc;
st.push(n);
in_stack[n] = 1;
for (auto it : M[n]) {
if (idx[it] == 0) {
tarjan(it);
lowlink[n] = min(lowlink[n], lowlink[it]);
} else if (in_stack[it])
lowlink[n] = min(lowlink[n], lowlink[it]);
}
if (idx[n] == lowlink[n]) {
aux.clear();
int node;
do {
aux.push_back(node = st.top());
in_stack[node] = 0;
st.pop();
} while (node != n);
sol.push_back(aux);
}
}
int main() {
int n, m, x, y;
in >> n >> m;
for (int i = 1; i <= m; i++) {
in >> x >> y;
M[x].push_back(y);
}
for (int i = 1; i <= n; i++)
if (idx[i] == 0)
tarjan(i);
out << sol.size() << '\n';
for (int i = 0; i < sol.size(); i++) {
for (int j = 0; j < sol[i].size(); j++)
out << sol[i][j] << " ";
out << '\n';
}
return 0;
}