Pagini recente » Cod sursa (job #2672079) | Cod sursa (job #3204652) | Cod sursa (job #1752389) | Cod sursa (job #2622448) | Cod sursa (job #3041006)
#include <bits/stdc++.h>
using namespace std;
#define FILE "ctc"
ifstream in(FILE".in");
ofstream out(FILE".out");
#define M 100100
#define N 100100
struct el {
int vf, urm;
};
el g_s[2 * M], g_p[2 * M], ctc[N];
int lst_s[N], lst_p[N], g_s_topo[N], lst_c[N], c[N];
int n, n_s_top, m, nrs, nrp, nrc, n_c;
bool viz[N];
void adauga(int u, int v, el g[], int lst[], int &nr) {
nr++;
g[nr].vf = v;
g[nr].urm = lst[u];
lst[u] = nr;
}
//parcurgere for(int p = lst[u]; p != 0; p = v[p].urm) { int v = v[p].vf; }
void dfs_ini(int u)
{
viz[u] = 1;
for(int p=lst_s[u]; p!=0; p=g_s[p].urm)
{
int v = g_s[p].vf;
if(!viz[v])
dfs_ini(v);
}
g_s_topo[++n_s_top] = u;
}
void dfs_trans(int u)
{
c[u] = n_c;
for(int p=lst_p[u]; p!=0; p=g_p[p].urm)
{
int v = g_p[p].vf;
if(c[v] == 0)
dfs_trans(v);
}
}
int main()
{
in >> n >> m;
for(int i=0; i<m; i++)
{
int u, v;
in >> u >> v;
adauga(u, v, g_s, lst_s, nrs);
adauga(v, u, g_p, lst_p, nrp);
}
in.close();
for(int i=1; i<=n; i++)
if(!viz[i])
dfs_ini(i);
for(int i=n_s_top; i>=1; i--)
if(c[g_s_topo[i]] == 0)
{
n_c++;
dfs_trans(g_s_topo[i]);
}
out << n_c << '\n';
for(int i=n; i>=1; i--)
{
adauga(c[i], i, ctc, lst_c, nrc); //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 u = ctc[p].vf;
out << u << " ";
}
out << '\n';
}
out.close();
}