Pagini recente » Cod sursa (job #249197) | Cod sursa (job #2895231) | Cod sursa (job #966104) | Cod sursa (job #3213735) | Cod sursa (job #580073)
Cod sursa(job #580073)
#include <fstream>
#include <vector>
using namespace std;
#define NMAX 100050
bool viz[NMAX];
int S[NMAX], N, nr, n, m;
vector <int> G[NMAX], GT[NMAX], CTC[NMAX];
void dfs1 (int), dfs2 (int), kosaraju (), citire (), afisare ();
int main () {
citire ();
kosaraju ();
afisare ();
return 0;
}
void dfs1 (int nod) {
viz[nod] = 1;
for (vector <int>::iterator it = G[nod].begin (); it != G[nod].end (); it++)
if (!viz[*it]) dfs1 (*it);
S[++N] = nod;
}
void dfs2 (int nod) {
viz[nod] = 0; CTC[nr].push_back (nod);
for (vector <int>::iterator it = GT[nod].begin (); it != GT[nod].end (); it++)
if (viz[*it]) dfs2 (*it);
}
void kosaraju () {
for (int i = 1; i <= n; i++)
if (!viz[i]) dfs1 (i);
for ( ; N > 0; N--)
if (viz[ S[N] ]) {
nr++;
dfs2 (S[N]);
}
}
void citire () {
ifstream f ("ctc.in");
int i, x, y;
f >> n >> m;
for (i = 1; i <= m; i++) {
f >> x >> y;
G[x].push_back (y);
GT[y].push_back (x);
}
f.close ();
}
void afisare () {
ofstream g ("ctc.out");
g << nr << "\n";
for (int i = 1; i <= nr; i++) {
for (vector <int>::iterator it = CTC[i].begin (); it != CTC[i].end (); it++)
g << *it << " ";
g << "\n";
}
}