Pagini recente » Cod sursa (job #2227655) | Cod sursa (job #2903455) | Cod sursa (job #591661) | Cod sursa (job #216441) | Cod sursa (job #2842041)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int NMAX = 100001,
MMAX = 200001;
struct nod
{
int info;
nod *urm;
};
nod *G[NMAX],
*GT[NMAX],
*CTC[NMAX];
bool viz[NMAX];
int N, M, S[NMAX], vf, nrc;
void add(nod *&p, int val)
{
nod *r = new nod;
r->info = val;
r->urm = p;
p = r;
}
void citire()
{
f >> N >> M;
for(int i = 1; i <= M; i++)
{
int x, y;
f >> x >> y;
add(G[x], y);
add(GT[y], x);
}
}
void DFS(int Nod)
{
viz[Nod] = 1;
for(nod *p = G[Nod]; p; p = p->urm)
if(!viz[p->info])
DFS(p->info);
S[++vf] = Nod;
}
void DFST(int Nod)
{
viz[Nod] = 0;
add(CTC[nrc], Nod);
for(nod *p = GT[Nod]; p; p = p->urm)
if(viz[p->info])
DFST(p->info);
}
void afisare()
{
g << nrc << '\n';
for(int i = 1; i <= nrc; i++)
{
for(nod*p = CTC[i]; p; p = p->urm)
g << p->info << ' ';
g << '\n';
}
}
int main()
{
citire();
for(int i = 1; i <= N; i++)
if(!viz[i])
DFS(i);
while(vf)
{
int curent = S[vf--];
if(viz[curent])
{
nrc++;
DFST(curent);
}
}
afisare();
return 0;
}