Pagini recente » Atasamentele paginii Profil Denis_Voc | Cod sursa (job #734160) | Borderou de evaluare (job #794309) | Borderou de evaluare (job #24019) | Cod sursa (job #1669987)
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 100005
using namespace std;
vector<int> G[NMAX], Gt[NMAX], L, Sol[NMAX];
int N, M, viz[NMAX], k, c[NMAX], NrComp;
void Read();
void Solve();
void Write();
void visit(int node); //Topological sort
void create_Strongly_Conn_Component(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_Strongly_Conn_Component(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_Strongly_Conn_Component(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_Strongly_Conn_Component(neigh, component);
}
}
void Write()
{
cout<<NrComp<<'\n';
for(int i=1; i<=NrComp; i++) {
for(int j=0; j < Sol[i].size(); j++)
cout<<Sol[i][j]<<' ';
cout<<'\n';
}
}
void Read()
{
freopen("ctc.in","rt",stdin);
freopen("ctc.out","wt",stdout);
int x, y;
scanf("%d%d",&N, &M);
for(int i=1; i<=M; i++) {
scanf("%d%d", &x, &y);
G[x].push_back(y);
Gt[y].push_back(x);
}
}