Pagini recente » Cod sursa (job #212257) | Cod sursa (job #1088694) | Cod sursa (job #2566350) | Cod sursa (job #2909221) | Cod sursa (job #2540882)
#define DM 100001
#define inf 0x3f3f3f3f
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
ifstream fi ("ctc.in");
ofstream fo ("ctc.out");
bool ins[DM];
int n, m, a, b, idx[DM], ctc[DM], total, midx[DM], nw;
stack <int> st;
vector <int> v[DM], sol[DM];
void discover(int nod) {
idx[nod] = midx[nod] = ++nw;
ins[nod] = 1;
st.push(nod);
for (auto i:v[nod]) {
if (idx[i] < idx[nod] && ins[i]) {
midx[nod] = min(idx[i], midx[nod]);
} else if (idx[i] == inf) {
discover(i);
midx[nod] = min(midx[i], midx[nod]);
}
}
if (midx[nod] == idx[nod]) {
++total;
while (st.top() != nod) {
ctc[st.top()] = total;
st.pop();
}
ctc[nod] = total;
st.pop();
}
ins[nod] = 0;
}
int main() {
fi >> n >> m;
// cout << n << ' ' << m;
for (int i = 1; i <= n; ++i)
idx[i] = inf;
for (int i = 1; i <= m; ++i) {
fi >> a >> b;
v[a].push_back(b);
}
for (int i = 1; i <= n; ++i)
if (!ctc[i])
discover(i);
// cout << n << '\n';
fo << total;
for (int i = 1; i <= n; ++i)
sol[ctc[i]].push_back(i);
for (int i = 1; i <= total; ++i)
for (auto j:sol[i])
fo << j << " \n"[j==sol[j].back()];
return 0;
}