Pagini recente » Cod sursa (job #800266) | Cod sursa (job #2869017) | Cod sursa (job #849576) | Cod sursa (job #2689199) | Cod sursa (job #802800)
Cod sursa(job #802800)
#include <fstream>
#include <vector>
#define pb push_back
using namespace std;
ifstream f("ctc.in");
ofstream h("ctc.out");
int n,m,nr,v[100001];
bool sel[100001];
vector <int> g[100001],gt[100001],val;
vector < vector<int> > vec;
void read()
{
int x,y,i;
f>>n>>m;
for (i=1;i<=m;i++)
{
f>>x>>y;
g[x].pb(y);
gt[y].pb(x);
}
}
void DFplus (int x)
{
vector <int> :: iterator it;
sel[x]=true;
for (it=g[x].begin();it!=g[x].end();it++)
{
if (!sel[*it])
{
DFplus(*it);
}
}
v[++nr]=x;
}
void DFminus (int x)
{
vector <int> :: iterator it;
sel[x]=false;val.pb(x);
for (it=gt[x].begin();it!=gt[x].end();it++)
{
if (sel[*it])
{
DFminus(*it);
}
}
}
void solve ()
{
for (int i=1;i<=n;i++)
if (!sel[i]) DFplus(i);
while (nr)
{
if (sel[v[nr]])
{
val.clear();
DFminus(v[nr]);
vec.pb(val);
}
nr--;
}
}
int main()
{
vector < vector<int> > :: iterator it;
vector <int> :: iterator it1;
read();
solve();
h<<vec.size()<<'\n';
for (it=vec.begin();it!=vec.end();it++)
{
for (it1=it->begin();it1!=it->end();it1++)
h<<*it1<<' ';
h<<'\n';
}
return 0;
}