Pagini recente » Istoria paginii runda/cnrv_oji_1 | Cod sursa (job #1784115) | Cod sursa (job #2209226) | Cod sursa (job #1741770) | Cod sursa (job #2414260)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
int f[100001], s[200001], t, n, m, nctc;
bool viz[100001];
ifstream fi("ctc.in");
ofstream fout("ctc.out");
vector <int> v[100001], vt[100001], scc[100001];
/// In s retinem nodurile sortate descrescator dupa timpii finali.
void dffinal(int i) {
int c;
viz[i] = true; t++;
for (c = 0; c < v[i].size(); c++)
if (not viz[v[i][c]]) /// Nu a fost vizitat.
dffinal(v[i][c]);
t++; f[i] = t; s[t] = i;
}
void dfsc(int i) {
int c;
scc[nctc].push_back(i); /// Retinem nodul.
viz[i] = true; /// Il consideram vizitat.
for (c = 0; c < vt[i].size(); c++)
if (not viz[vt[i][c]]) /// Nu a fost vizitat.
dfsc(vt[i][c]); /// Parcurgem in adancime.
}
int main() {
int x, y, i, nc, l, c;
fi >> n >> m;
for (i = 1; i <= m; i++) {
fi >> x >> y;
v[x].push_back (y);
vt[y].push_back (x);
}
t = 0;
for (i = 1; i <= n; i++) // Determinam timpii finali.
if (not viz[i])
dffinal(i);
memset(viz, 0, 100001 * sizeof(bool)); // Reinitializam pentru parcurgerea care urmeaza.
for (l = t; l >= 0; l--) { /// Parcurgem sirul sortat al nodurilor.
if (s[l] != 0) { /// S-ar putea ca locului l sa nu ii corespunda un nod.
nc = s[l]; /// nodul curent
if (not viz[nc]) { /// Nu a fost vizitat.
nctc++; /// inca o componenta
dfsc(nc); /// Parcurgem o componenta.
}
}
}
fout << nctc << '\n';
for (c = 1; c <= nctc; c++) { // Pentru fiecare componenta
for (n = 0; n < scc[c].size(); n++) // nodul din componenta
fout << scc[c][n] << ' ';
fout << '\n';
}
return 0;
}