Pagini recente » Cod sursa (job #3178272) | Cod sursa (job #910185) | Borderou de evaluare (job #2828305) | Cod sursa (job #556753) | Cod sursa (job #3278005)
#include <fstream>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n, m, t[2][500100], start[500100], gt[2][500100], gstart[500100], timp[500100], nr, ans[500100], a;
bool viz[500100], vizt[500100];
void citire()
{
int x, y;
in>>n>>m;
for(int i=1; i<=m; i++)
{
in>>x>>y;
t[0][i]=y;
t[1][i]=start[x];
start[x]=i;
gt[0][i]=x;
gt[1][i]=gstart[y];
gstart[y]=i;
}
}
void dfst(int x)
{
int man=gstart[x];
vizt[x]=1;
while(man)
{
if(vizt[gt[0][man]]==0)
dfst(gt[0][man]);
man=gt[1][man];
}
timp[++nr]=x;
}
void dfs(int x)
{
int man=start[x];
viz[x]=1;
while(man)
{
if(viz[t[0][man]]==0)
dfs(t[0][man]);
man=t[1][man];
}
ans[++a]=x;
}
int main()
{
int conex=0;
citire();
for(int i=1; i<=n; i++)
if(vizt[i]==0)
dfst(i);
for(int i=nr; i>0; i--)
{
if(viz[timp[i]]==0)
{
conex++;
dfs(timp[i]);
ans[++a]=-1;
}
}
out<<conex<<'\n';
for(int i=1; i<=a; i++)
{
if(ans[i]!=-1)
out<<ans[i]<<" ";
else out<<'\n';
}
return 0;
}