Pagini recente » Cod sursa (job #2669363) | Cod sursa (job #660177) | Cod sursa (job #3291778) | Cod sursa (job #2520593) | Cod sursa (job #3041003)
#include <fstream>
using namespace std;
const int N = 1e5;
const int M = 2e5;
struct element
{
int vf, urm;
};
element v_s[M+1], v_p[M+1], ctc[N+1];
int lst_s[N+1], lst_p[N+1], lst_c[N+1];
int n, m, nr_s, nr_p, nr_c;
int v_s_top[N+1], n_s_top, c[N+1], n_c;
bool viz[N+1];
void adauga(int x, int y, element v[], int lst[], int &nr)
{
nr++;
v[nr].vf = y;
v[nr].urm = lst[x];
lst[x] = nr;
}
void dfs_ini(int x)
{
viz[x] = 1;
for (int p = lst_s[x]; p != 0; p = v_s[p].urm)
{
int y = v_s[p].vf;
if (!viz[y])
{
dfs_ini(y);
}
}
v_s_top[++n_s_top] = x;
}
void dfs_trans(int x)
{
c[x] = n_c;
for (int p = lst_p[x]; p != 0; p = v_p[p].urm)
{
int y = v_p[p].vf;
if (c[y] == 0)
{
dfs_trans(y);
}
}
}
int main()
{
ifstream in("ctc.in");
ofstream out("ctc.out");
in >> n >> m;
for (int i = 0; i < m; i++)
{
int x, y;
in >> x >> y;
adauga(x, y, v_s, lst_s, nr_s);
adauga(y, x, v_p, lst_p, nr_p);
}
///pasul 1
for (int i = 1; i <= n; i++)
{
if (!viz[i])
{
dfs_ini(i);
}
}
///pasul 2
for (int i = n_s_top; i >= 1; i--)
{
if (c[v_s_top[i]] == 0)
{
n_c++;
dfs_trans(v_s_top[i]);
}
}
out << n_c << "\n";
for (int i = n; i >= 1; i--)
{
adauga(c[i], i, ctc, lst_c, nr_c);///il adaug pe i in lista c[i]
}
for (int i = 1; i <= n_c; i++)
{
for (int p = lst_c[i]; p != 0; p = ctc[p].urm)
{
int x = ctc[p].vf;
out << x << " ";
}
out << "\n";
}
in.close();
out.close();
return 0;
}