Pagini recente » Cod sursa (job #2676899) | Cod sursa (job #1271293) | Cod sursa (job #3227799) | Cod sursa (job #1278939) | Cod sursa (job #2236575)
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> G[100005],IG[100005],Sol[100005];
stack <int> Stack;
int Viz[100005],N,M,Nr;
void Read(){
fin>>N>>M;
for(int i=1;i<=M;i++){
int X,Y;
fin>>X>>Y;
G[X].push_back(Y);
IG[Y].push_back(X);
}
}
void DFS(int Nod){
Viz[Nod]=1;
for(int i=0;i<G[Nod].size();i++)
if(!Viz[G[Nod][i]])
DFS(G[Nod][i]);
Stack.push(Nod);
}
void IDFS(int Nod){
Viz[Nod]=0;
Sol[Nr].push_back(Nod);
for(int i=0;i<IG[Nod].size();i++)
if(Viz[IG[Nod][i]])
IDFS(IG[Nod][i]);
}
void Kosaraju(){
for(int i=1;i<=N;i++)
if(!Viz[i])
DFS(i);
while(!Stack.empty()){
if(Viz[Stack.top()]){
Nr++;
IDFS(Stack.top());
}
Stack.pop();
}
}
int main(){
Read();
Kosaraju();
fout<<Nr<<'\n';
for(int i=1;i<=Nr;i++){
for(int j=0 ; j < Sol[i].size() ; j++)
fout<<Sol[i][j]<<' ';
fout<<'\n';
}
}