Pagini recente » Cod sursa (job #897189) | Monitorul de evaluare | Cod sursa (job #2351698) | Cod sursa (job #315230) | Cod sursa (job #752657)
Cod sursa(job #752657)
#include <fstream>
#include <vector>
#include <cstring>
#define pb push_back
using namespace std;
ifstream f("ctc.in");
ofstream G("ctc.out");
bool sel[200010];
int stiva[200010],m,n,i,nc,nr,x,y;
vector<int> g[200010],gt[200010];
void dfs (int x)
{
int i;
sel[x]=true;
for(i=0;i<g[x].size();++i)
if (!sel[g[x][i]]) dfs(g[x][i]);
stiva[++nr]=x;
}
void dfts (int x, bool k)
{
int i;
sel[x]=true;
if (k) G<<x<<' ';
for(i=0; i<gt[x].size();i++)
if (!sel[gt[x][i]]) dfts(gt[x][i], k);
}
int main ()
{
f>>n>>m;
for (i=1;i<=m;i++)
{
f>>x>>y;
g[x].pb(y);
gt[y].pb(x);
}
nc=nr=0;
nr=0; nc=0;
for (i=1;i<=200010;i++) sel[i]=false;
for(i=1;i<=n;i++)
if (!sel[i]) dfs(i);
for (i=1;i<=200010;i++) sel[i]=false;
for(i=n;i>0;i--)
if (!sel[stiva[i]])
{
dfts(stiva[i], false);
nc++;
}
G<<nc<<'\n';
for (i=1;i<=200010;i++) sel[i]=false;
for(i=n;i>0;i--)
if (!sel[stiva[i]])
{
dfts(stiva[i], true);
G<<'\n';
}
return 0;
}