Pagini recente » Cod sursa (job #3236968) | Cod sursa (job #1853617) | Cod sursa (job #1901068) | Cod sursa (job #337381) | Cod sursa (job #711045)
Cod sursa(job #711045)
#include<fstream>
using namespace std;
#define lung 100001
ifstream fin("ctc.in");
ofstream fout("ctc.out");
struct nod{int val;
nod *next;
};
nod *transp[lung],*v[lung],*rasp[lung],*q;
int i,n,m,nr,timp[lung],ordine[lung],final1;
bool viz1[lung],viz[lung];
inline void df(int x)
{nod *q=transp[x],*p;
if (q)
{ while (q)
{ if (!viz1[q->val])
{ viz1[q->val] = true;
p = new nod;
p -> val = q -> val;
p -> next = rasp[nr];
rasp[nr]= p;
df(q->val);
}
q = q -> next;
}
}
}
inline void final(int x)
{nod *q=v[x];
if (q)
{ while (q)
{ if (!viz[q->val])
{ viz[q->val] = true;
final(q->val);
++final1;
}
q = q -> next;
}
timp[x] = final1;
}
}
int main()
{int a,b,i;
fin >> n >> m;
for (i=1;i<=m;++i)
{ fin >> a >> b;
q = new nod;
q -> val = b;
q -> next = v[a];
v[a] = q;
q = new nod;
q -> val = a;
q -> next = transp[b];
transp[b] = q;
}
for (i=1;i<=n;++i)
if (!viz[i])
{ viz[i] = true;
final(i);
}
for (i=1;i<=n;++i)
ordine[n-timp[i]] = i;
for (i=1;i<=n;++i)
if (!viz1[ordine[i]])
{ ++nr;
viz1[ordine[i]] = true;
q = new nod;
q -> val = ordine[i];
q -> next = rasp[nr];
rasp[nr] = q;
df(ordine[i]);
}
fout << nr << '\n';
for (i=1;i<=nr;++i)
{ q = rasp[i];
while (q)
{ fout << q -> val << " ";
q = q -> next;
}
fout << '\n';
}
return 0;
}