Pagini recente » Cod sursa (job #1283592) | Cod sursa (job #1235170) | Cod sursa (job #2937580) | Cod sursa (job #2228047) | Cod sursa (job #2153248)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int MaxN = 100005;
int n, m;
int onst[MaxN], low[MaxN];
bitset<MaxN> viz;
vector<int> gr[MaxN], tati[MaxN];
stack<int> st;
vector<vector<int> > comps;
void Ctc(int node) {
viz[node] = 1;
st.push(node);
onst[node] = st.size();
low[node] = onst[node];
for (auto son: gr[node]) {
if (!viz[son]) {
Ctc(son);
low[node] = min(low[node], low[son]);
}
else if (onst[son]) low[node] = min(low[node], onst[son]);
}
if (low[node] == onst[node]) {
vector<int> v;
while (st.top() != node) {
v.push_back(st.top());
onst[st.top()] = 0;
st.pop();
}
st.pop();
v.push_back(node);
onst[node] = 0;
comps.push_back(v);
}
}
int main() {
f >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y;
f >> x >> y;
gr[x].push_back(y);
}
for (int i = 1; i <= n; ++i) if (!viz[i]) Ctc(i);
g << comps.size() << '\n';
for (auto v: comps) {
for (auto x: v) g << x << ' ';
g << '\n';
}
return 0;
}