Pagini recente » Cod sursa (job #776708) | Cod sursa (job #2411388) | Cod sursa (job #3278240) | Cod sursa (job #287296) | Cod sursa (job #1992170)
#include <fstream>
#include <cstring>
#include <stack>
using namespace std;
ifstream F("ctc.in");
ofstream G("ctc.out");
int v[100003], n, m, K, k, w[100003], x, y, idx[100003], ll[100003], t = 1;
struct node{int info; node *urm;} *L[100002], *l[100003], *q;
stack <int> s;
void dfs(int nod)
{
v[nod] = 1;
s.push(nod);
node *p;
p = L[nod]->urm;
idx[nod] = ll[nod] = t;
t ++;
while(p != NULL)
{
if(!idx[p->info]) dfs(p->info), ll[nod] = min(ll[p->info], ll[nod]);
else if(v[p->info]) ll[nod] = min(ll[p->info], ll[nod]);
p=p->urm;
}
if(idx[nod] == ll[nod])
{
++ K;
do
{
q = new node;
q->urm = l[K]->urm;
x = s.top();
q->info = x;
s.pop();
v[x] = 0;
l[K]->urm = q;
}while(x != nod);
}
}
int main()
{
F >> n >> m;
for(int i = 1; i <= n; ++ i)
L[i] = new node, L[i]->urm = NULL;
for(int i = 0; i < m; ++ i)
{
F >> x >> y;
q = new node;
q->urm = L[x]->urm;
q->info = y;
L[x]->urm = q;
}
for(int i = 1; i <= n; ++ i)
l[i] = new node, l[i]->urm = NULL;
for(int i = 1; i <= n; ++ i)
if(!idx[i]) dfs(i);
G << K<< '\n';
for(int i = 1; i <= K; ++ i)
{
q = l[i]->urm;
while(q != NULL)
{
G << q->info << " ";
q=q->urm;
}
G << '\n';
}
return 0;
}