Pagini recente » Cod sursa (job #1303423) | Cod sursa (job #3281241) | Cod sursa (job #589347) | Cod sursa (job #1051030) | Cod sursa (job #2117755)
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> G[NMAX], Gt[NMAX], L, Sol[NMAX];
int N, M, viz[NMAX], k, c[NMAX], NrComp,x,y;
void Read();
void Solve();
void Write();
void visit(int node); //Topological sort
void create(int node, int component);
int main()
{
Read();
Solve();
Write();
}
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 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 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';
}
}
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);
}
}