Pagini recente » Cod sursa (job #2927002) | Cod sursa (job #2209431) | Cod sursa (job #2749832) | Cod sursa (job #1811684) | Cod sursa (job #2154091)
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,viz[nmax],nrcomp,x,y,c[nmax];
vector < int > Sol[nmax],Gt[nmax],G[nmax],L;
void read()
{
fin>>n>>m;
for(int i =1 ; i <= m ; i ++)
{
fin>>x>>y;
G[x].push_back(y);
Gt[y].push_back(x);
}
}
void visit(int node)
{
if(viz[node]) return ;
viz[node]=1;
for(int i = 0 ; i < G[node].size(); i++)
visit(G[node][i]);
L.push_back(node);
}
void create(int node, int component)
{
c[node]=component;
Sol[component].push_back(node);
for(int i = 0 ; i < Gt[node].size(); i++)
{
int neigh=Gt[node][i];
if(!c[neigh])
create(neigh,component);
}
}
void solve()
{
for(int node = 1; node <= n ; node ++)
visit(node);
while(!L.empty())
{
if(c[L.back()]==0)
create(L.back(),++nrcomp);
L.pop_back();
}
}
void write()
{
fout<<nrcomp<<'\n';
for(int i = 1; i <= nrcomp; i++)
{
for(int j =0; j < Sol[i].size(); j++)
{
fout<<Sol[i][j]<<" ";
}
fout<<'\n';
}
}
int main()
{
read();
solve();
write();
return 0;
}