Pagini recente » Cod sursa (job #544491) | Cod sursa (job #2537478) | Cod sursa (job #879965) | Cod sursa (job #2691626) | Cod sursa (job #1637855)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int N_max = 100005;
const int M_max = 200005;
int vf1[M_max];
int urm1[M_max];
int lst1[N_max];
int nr1;
int vf2[M_max];
int urm2[M_max];
int lst2[N_max];
int nr2;
int vf3[M_max];
int urm3[M_max];
int lst3[N_max];
int nr3;
int sol;
int C[N_max];
int K;
bool viz1[N_max];
bool viz2[N_max];
int N, M;
void adauga_1(int x, int y)
{
// ADAUGA IN LISTA LUI x pe y
nr1++;
vf1[nr1] = y;
urm1[nr1] = lst1[x];
lst1[x] = nr1;
}
void adauga_2(int x, int y)
{
// ADAUGA IN LISTA LUI x pe y
nr2++;
vf2[nr2] = y;
urm2[nr2] = lst2[x];
lst2[x] = nr2;
}
void adauga_3(int x, int y)
{
// ADAUGA IN LISTA LUI x PE y
nr3++;
vf3[nr3] = y;
urm3[nr3] = lst3[x];
lst3[x] = nr3;
}
void dfs1(int x)
{
int p, y;
viz1[x] = true;
// PARCURG VECINII y AI LUI x
p = lst1[x];
while(p != 0)
{
y = vf1[p];
if(!viz1[y]) dfs1(y);
p = urm1[p];
}
C[++K] = x;
}
void dfs2(int x)
{
int p, y;
viz2[x] = true;
adauga_3(sol, x);
// PARCURG VECINII y AI LUI x
p = lst2[x];
while(p != 0)
{
y = vf2[p];
if(!viz2[y]) dfs2(y);
p = urm2[p];
}
}
int main()
{
int i, x, y, p;
in >> N >> M;
for(i = 1; i <= M; i++)
{
in >> x >> y;
adauga_1(x, y);
adauga_2(y, x); // GRAF TRANSPUS
}
for(i = 1; i <= N; i++)
if(!viz1[i]) dfs1(i);
for(i = N; i >= 1; i--)
if(!viz2[ C[i] ])
{
sol++;
dfs2(C[i]);
}
out << sol << '\n';
for(x = 1; x <= sol; x++)
{
// PARCURG LISTA VECINILOR LUI x
p = lst3[x];
while(p != 0)
{
y = vf3[p];
out << y << " ";
p = urm3[p];
}
out << '\n';
}
return 0;
}