Pagini recente » Cod sursa (job #1192457) | Cod sursa (job #2066386) | Cod sursa (job #1376588) | Cod sursa (job #1990567) | Cod sursa (job #1662416)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int N = 100005;
int n, m, x, y, nr=0, nrc=0;
int urm[2*N], vf[2*N], lst[N], urmt[N*2], vft[N*2], lstt[N*2], vfc[N*2], urmc[N*2], lstc[N*2], c[N];
bool viz[N];
void Adaugatc(int nc, int x)
{
nrc++;
vfc[nrc] = x;
urmc[nrc] = lstc[nc];
lstc[nc] = nrc;
}
void Adauga(int x, int y)
{
nr++;
vf[nr] = y;
urm[nr] = lst[x];
lst[x] = nr;
vft[nr] = x;
urmt[nr] = lstt[y];
lstt[y] = nr;
}
void dfst(int x)
{
//out << x << " ";
viz[x] = true;
int p, y;
p = lstt[x];
Adaugatc(nr, x);
while(p != 0)
{
y = vft[p];
if(!viz[y])
dfst(y);
p = urmt[p];
}
}
void dfs(int x)
{
viz[x] = true;
int p, y;
p = lst[x];
while(p != 0)
{
y = vf[p];
if(!viz[y])
dfs(y);
p = urm[p];
}
c[++nr]=x;
}
int main()
{
in>>n>>m;
for(int i = 1; i <= m; i++)
{
in>>x>>y;
Adauga(x, y);
}
nr = 0;
for(int i = 1; i <= n; i++)
{
if(!viz[i])
dfs(i);
}
for(int i = 1; i <= n; i++)
{
viz[i] = false;
}
nr = nrc = 0;
for(int i = n; i >= 1; i--)
{
if(!viz[c[i]])
{
nr++;
dfst(c[i]);
//out << "\n";
}
}
out<<nr<<"\n";
int p;
for(int i = 1; i <= nr; i++)
{
p = lstc[i];
while(p != 0)
{
x = vfc[p];
out<<x<<' ';
p = urmc[p];
}
out<<"\n";
}
return 0;
}