Pagini recente » Cod sursa (job #3283791) | Profil MihaiG | Cod sursa (job #407740) | Istoria paginii utilizator/obliterator | Cod sursa (job #2012528)
#include <fstream>
#include <stack>
#include <vector>
#include <bitset>
#define in "ctc.in"
#define out "ctc.out"
#define N 100003
using namespace std;
ifstream fin(in);
ofstream fout(out);
int n,m,x,y;
stack < int > st;
vector < int > g[N],gt[N];
int nctc;
vector < int > sol[N];
bitset <N> f;
void read_input()
{
fin>>n>>m;
while(m--)
{
fin>>x>>y;
g[x].push_back(y);
gt[y].push_back(x);
}
}
inline void DFS(int nod)
{
f[nod] = 1;
vector < int >::iterator it;
for(it = g[nod].begin(); it != g[nod].end(); ++it)
if(!f[*it])
{
int x = *it;
DFS(x);
}
st.push(nod);
}
inline void DFSt(int nod)
{
sol[nctc].push_back(nod);
f[nod] = 1;
vector < int >::iterator it;
for(it = gt[nod].begin(); it != gt[nod].end(); ++it)
if(!f[*it]) DFSt(*it);
}
void solve()
{
for(int i=1; i<=n; ++i)
if(!f[i])
DFS(i);
f.reset();
while(!st.empty())
{
int x = st.top();
if(!f[x])
{
DFSt(x);
++nctc;
}
st.pop();
}
}
void write_output()
{
fout<<nctc<<"\n";
for(int i=0; i<nctc; ++i)
{
vector < int >::iterator it;
for(it = sol[i].begin(); it!= sol[i].end(); ++it)
fout<<*it<<" ";
fout<<"\n";
}
}
int main()
{
read_input();
solve();
write_output();
fin.close(); fout.close();
return 0;
}