Pagini recente » Cod sursa (job #2632320) | Cod sursa (job #1031394) | Cod sursa (job #2485978)
#define DM 100001
#include <fstream>
#include <set>
#include <vector>
using namespace std;
ifstream fi ("ctc.in");
ofstream fo ("ctc.out");
bool in_stack[DM], was_checked[DM];
int n, m, a, b, next_ctc, actc[DM], crsp[DM];
set <int> normalize;
vector <int> v[DM], s, rev[DM];
void dfs(int x, int comp) {
// found cycle
if (in_stack[x]) {
int ctc = comp;
if (!ctc)
ctc = ++next_ctc;
actc[x] = ctc;
for (int i = s.size() - 1; i >= 0; --i) {
if (s[i] == x)
break;
actc[s[i]] = ctc;
}
return;
}
// marked node
was_checked[x] = 1;
in_stack[x] = 1;
s.push_back(x);
// propagated the dfs
for (auto i:v[x])
dfs(i, actc[x]);
in_stack[x] = 0;
s.pop_back();
}
int main() {
// next_ctc poate fi mai mare decat nr real de componente, in cazul in care
// o componenta tare conexa e invaluita de o alta, asa ca am nevoie de o
// normalizare a numerelor corespunzatoare componentelor -- nu stiu cum altfel
// sa repar chestia asta
fi >> n >> m;
for (int i = 1; i <= m; ++i) {
fi >> a >> b;
v[a].push_back(b);
}
for (int i = 1; i <= n; ++i)
if (!was_checked[i])
dfs(i, 0);
for (int i = 1; i <= n; ++i)
normalize.insert(actc[i]);
next_ctc = 0;
for (auto i:normalize)
crsp[i] = ++next_ctc;
for (int i = 1; i <= n; ++i)
rev[crsp[actc[i]]].push_back(i);
fo << next_ctc << '\n';
for (int i = 1; i <= next_ctc; ++i) {
for (auto j:rev[i])
fo << j << ' ';
fo << '\n';
}
return 0;
}