Pagini recente » Cod sursa (job #820305) | Cod sursa (job #2424354) | Cod sursa (job #58400) | Cod sursa (job #430776) | Cod sursa (job #2118454)
#include <fstream>
#include <list>
#include <bitset>
#include <stack>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int nmax=100005, white=0, gray=1, black=2;
int n, m;
int colour[nmax];
list <int> g[nmax], gt[nmax];
stack <int> s;
vector <int> sol[nmax];
bitset <nmax> vis;
void read_data()
{
int i, x, y;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>x>>y;
g[x].push_back(y);
gt[y].push_back(x);
}
}
inline void dfs(int node)
{
list <int> :: iterator it;
colour[node]=gray;
for(it=g[node].begin();it!=g[node].end();it++)
if(colour[*it]==white)
dfs(*it);
s.push(node);
colour[node]=black;
}
inline void DFS(int node, int k)
{
list <int> :: iterator it;
vis[node]=true;
colour[node]=white;
for(it=gt[node].begin();it!=gt[node].end();it++)
if(colour[*it]==black)
DFS(*it,k);
sol[k].push_back(node);
}
void solve()
{
int i, k=0, node;
for(i=1;i<=n;i++)
if(!vis[i])
{
dfs(i);
while(!s.empty())
{
node=s.top();
s.pop();
if(!vis[node])
{
k++;
DFS(node,k);
}
}
}
fout<<k<<'\n';
vector <int> :: iterator it;
for(i=1;i<=k;i++)
{
for(it=sol[i].begin();it!=sol[i].end();it++)
fout<<*it<<' ';
fout<<'\n';
}
}
int main()
{
read_data();
solve();
}