Pagini recente » Cod sursa (job #3222057) | Cod sursa (job #2499239) | Cod sursa (job #828484) | Cod sursa (job #2011476) | Cod sursa (job #1992089)
#include <fstream>
#include <cstring>
using namespace std;
ifstream F("ctc.in");
ofstream G("ctc.out");
int v[100003], n, m, K = 1, k, w[100003], x, y;
struct node{int info; node *urm;} *L1[100003], *L[100002], *l[100003], *q;
void dfs(int nod)
{
v[nod] = 1;
node *p;
p = L[nod]->urm;
while(p != NULL)
{
if(!v[p->info]) dfs(p->info);
p=p->urm;
}
w[++ k] = nod;
}
void dfs1(int nod)
{
v[nod] = 1;
node *p;
p = L1[nod]->urm;
while(p != NULL)
{
if(!v[p->info]) dfs1(p->info);
p=p->urm;
}
q = new node;
q->urm = l[K]->urm;
q->info = nod;
l[K]->urm = q;
}
int main()
{
F >> n >> m;
for(int i = 1; i <= n; ++ i)
L[i] = new node, L[i]->urm = NULL;
for(int i = 1; i <= n; ++ i)
L1[i] = new node, L1[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;
q = new node;
q->urm = L1[y]->urm;
q->info = x;
L1[y]->urm = q;
}
for(int i = 1; i <= n; ++ i)
if(!v[i]) dfs(i);
for(int i = 1; i <= k; ++ i)
l[i] = new node, l[i]->urm = NULL;
memset(v, 0, sizeof(v));
for(int i = k; i > 0; -- i)
if(!v[w[i]])dfs1(w[i]), ++K;
G << K - 1<< '\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;
}