Pagini recente » Cod sursa (job #1100216) | Cod sursa (job #2506378) | Cod sursa (job #2919648) | Cod sursa (job #2131980) | Cod sursa (job #529161)
Cod sursa(job #529161)
#include<fstream>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
#define pb push_back
#define p push
ofstream fout("ctc.out");
bool cmp(const int x, const int y)
{
return x < y;
}
void read();
void DF(int );
void write();
void DFT(int );
vector<vector<int> > a, at;
int n, m, nr = 1, nrc;
bool s[50002];
vector<int > sol[50002];
stack<int > S;
int main()
{
read();
for(int i = 1; i <= n; ++i)
if( !s[i] )
DF(i);
while( !S.empty() )
{
if( s[ S.top() ] )
{
nrc++;
DFT( S.top() );
S.pop();
}
else
S.pop();
}
write();
return 0;
}
void read()
{
ifstream fin("ctc.in");
fin >> n >> m;
a.resize(n+1);
at.resize(n+1);
int x, y;
for(int i = 1; i <= m; ++i)
{
fin >> x >> y;
a[x].pb(y);
at[y].pb(x); // a transpus
}
fin.close();
}
void DF(int x)
{
s[x] = 1;
vector<int >::iterator it;
for(it = a[x].begin(); it != a[x].end(); ++it)
if( !s[*it ] )
DF( *it );
S.p(x);
}
void DFT(int x)
{
sol[nrc].pb(x);
s[x] = 0;
for(vector<int >::iterator it = at[x].begin(); it != at[x].end(); ++it)
if( s[ *it ] == 1)
DFT( *it );
}
void write()
{
fout << nrc << '\n';
for(int i = 1; i <= nrc; i++)
{
sort(sol[i].begin(), sol[i].end(), cmp);
// int id = sol[i].size();
// fout << id <<" ";
vector<int >::iterator it, sf = sol[i].end();
for(it = sol[i].begin(); it != sf; ++it)
fout << *it <<" ";
fout << '\n';
}
}