Pagini recente » Cod sursa (job #1480988) | Cod sursa (job #1789782) | Cod sursa (job #2142603) | Cod sursa (job #120539) | Cod sursa (job #1357283)
#include <fstream>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int N = 100001, M = 200001;
int vf1[M], urm1[M], lst1[N], nr1 = 0;
int sortat[N], nr = 0;
int vf2[M], urm2[M], lst2[N], nr2 = 0;
bool ok[N];
int rez[2 * N];
int n, m;
void dfs_sortare(int x)
{
ok[x] = 1;
int p, y;
p = lst1[x];
while(p != 0)
{
y = vf1[p];
if(!ok[y])
dfs_sortare(y);
p = urm1[p];
}
sortat[++nr] = x;
}
void dfs_invers(int x)
{
rez[++nr] = x;
ok[x] = 1;
int y, p;
p = lst2[x];
while(p != 0)
{
y = vf2[p];
if(!ok[y])
dfs_invers(y);
p = urm2[p];
}
}
void citire()
{
in >> n >> m;
for(int i = 1; i <= m; i++)
{
int x, y;
in >> x >> y;
vf1[++nr1] = y;
urm1[nr1] = lst1[x];
lst1[x] = nr1;
vf2[++nr2] = x;
urm2[nr2] = lst2[y];
lst2[y] = nr2;
}
}
int main()
{
citire();
for(int i = 1; i <= n; i++)
if(!ok[i])
dfs_sortare(i);
for(int i = 1; i <= n; i++)
ok[i] = 0;
nr = 0;
int counter = 0;
for(int i = n; i >= 1; i--)
if(!ok[sortat[i]])
{
counter++;
dfs_invers(sortat[i]);
rez[++nr] = -1;
}
out << counter << '\n';
for(int i = 1; i <= nr; i++)
{
if(rez[i] == -1)
out << '\n';
else
out << rez[i] << ' ';
}
return 0;
}