Pagini recente » Cod sursa (job #1510497) | Cod sursa (job #734254) | Cod sursa (job #50390) | Cod sursa (job #1915724) | Cod sursa (job #1652218)
#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 vf_1[M_max];
int urm_1[M_max];
int lst_1[N_max];
int nr_1;
int vf_2[M_max];
int urm_2[M_max];
int lst_2[N_max];
int nr_2;
int vf_3[M_max];
int urm_3[M_max];
int lst_3[N_max];
int nr_3;
bool viz_1[N_max];
bool viz_2[N_max];
int C[N_max];
int K;
int sol;
int N, M;
void adauga_1(int x, int y)
{
// ADAUGA IN LISTA LUI x PE y
nr_1++;
vf_1[nr_1] = y;
urm_1[nr_1] = lst_1[x];
lst_1[x] = nr_1;
}
void adauga_2(int x, int y)
{
// ADAUGA IN LISTA LUI x PE y
nr_2++;
vf_2[nr_2] = y;
urm_2[nr_2] = lst_2[x];
lst_2[x] = nr_2;
}
void adauga_3(int x, int y)
{
// ADAUGA IN LISTA LUI x PE y
nr_3++;
vf_3[nr_3] = y;
urm_3[nr_3] = lst_3[x];
lst_3[x] = nr_3;
}
void dfs_1(int x)
{
int y, p;
viz_1[x] = true;
// PARCURG VECINII y AI LUI x
p = lst_1[x];
while(p != 0)
{
y = vf_1[p];
if(!viz_1[y]) dfs_1(y);
p = urm_1[p];
}
C[++K] = x;
}
void dfs_2(int x)
{
int y, p;
viz_2[x] = true;
//cout << x << " ";
adauga_3(sol, x);
// PARCURG VECINII y AI LUI x
p = lst_2[x];
while(p != 0)
{
y = vf_2[p];
if(!viz_2[y]) dfs_2(y);
p = urm_2[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(!viz_1[i]) dfs_1(i);
for(i = N; i >= 1; i--)
if(!viz_2[ C[i] ])
{
sol++;
dfs_2( C[i] );
}
out << sol << '\n';
for(x = 1; x <= sol; x++)
{
// PARCURG LISTA VECINILOR y LUI x
p = lst_3[x];
while(p != 0)
{
y = vf_3[p];
out << y << " ";
p = urm_3[p];
}
out << '\n';
}
return 0;
}