Pagini recente » Cod sursa (job #263840) | Cod sursa (job #2013309) | Cod sursa (job #901086) | Cod sursa (job #2851356) | Cod sursa (job #1165079)
#include <fstream>
#include <bitset>
#include <vector>
#define NMAX 100005
#define pb push_back
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, lg, nrTC;
vector <int> G[NMAX], GT[NMAX], sol[NMAX];
bitset <NMAX> viz;
int tsort[NMAX];
void citire()
{
int m, x, y;
fin >> n >> m;
while (m--)
{
fin >> x >> y;
G[x].pb(y);
GT[y].pb(x);
}
}
void DF (int x)
{
viz[x] = 1;
for (vector <int> :: iterator it = G[x].begin(); it != G[x].end(); ++it)
if (!viz[*it]) DF(*it);
tsort[++lg] = x;
}
void DFT (int x)
{
viz[x] = 1;
sol[nrTC].pb(x);
for (vector <int> :: iterator it = GT[x].begin(); it != GT[x].end(); ++it)
if (!viz[*it]) DFT(*it);
}
void ctc_tarjan()
{
for (int i = 1; i <= n; ++i)
if (!viz[i]) DF(i);
viz.reset();
for (int i = lg; i > 0; --i)
if (!viz[tsort[i]])
{
++nrTC;
DFT(tsort[i]);
}
}
void afisare()
{
fout << nrTC << '\n';
for (int i = 1; i <= nrTC; ++i)
{
for (vector <int> :: iterator it = sol[i].begin(); it != sol[i].end(); ++it)
fout << *it << " ";
fout << '\n';
}
}
int main()
{
citire();
ctc_tarjan();
afisare();
return 0;
}