Pagini recente » Cod sursa (job #2457926) | Cod sursa (job #651342) | Cod sursa (job #2704299) | Cod sursa (job #2644407) | Cod sursa (job #2671984)
#include <iostream>
#include <fstream>
#define Nmax 100000
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
long n, m, k, nr, t[Nmax], viz[Nmax];
struct elem
{
long inf;
elem *urm;
}*a[Nmax], *at[Nmax], *sol[Nmax];
void p1(long x)
{
for (elem *p = a[x]; p; p=p->urm)
if (viz[p->inf]==0)
{
viz[p->inf] = 1;
p1(p->inf);
}
k++;
t[k]=x;
}
void p2(long x, long nr)
{
elem *q = new elem;
q->inf = x;
q->urm = sol[nr];
sol[nr] = q;
viz[x] = -1;
for(elem *p=at[x];p;p=p->urm)
if(viz[p->inf] == 1)
p2(p->inf, nr);
}
int main()
{
long x, y;
f >> n >> m;
for (long i = 0; i < m; i++)
{
f >> x >> y;
elem *p = new elem;
p->inf = y;
p->urm = a[x];
a[x] = p;
p = new elem;
p->inf = x;
p->urm = at[y];
at[y] = p;
}
long i;
for (i = 1;i <= n;i++)
if (!viz[i])
{
viz[i] = 1;
p1(i);
}
for (i = n; i >= 1; i--)
if (viz[t[i]] == 1)
{
nr++;
p2(t[i],nr);
}
g << nr << '\n';
for (long i = 1; i <= nr; i++)
{
while(sol[i])
{
g << sol[i]->inf << " ";
sol[i] = sol[i]->urm;
}
g << '\n';
}
return 0;
}