Pagini recente » Cod sursa (job #1895703) | Cod sursa (job #3141399) | Cod sursa (job #345075) | Cod sursa (job #2903932) | Cod sursa (job #2796887)
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#define nmax 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
stack <int> S;
vector<int> G[nmax],GT[nmax],CTC[nmax];
int n, m, nrCTC;
int vizitat[nmax];
void Read()
{
fin >> n >> m;
for(int i = 1; i <= m; i++)
{
int x,y;
fin >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
}
void DFS(int nod)
{
vizitat[nod] = 1;
for(unsigned int i=0; i<G[nod].size();i++) {
int vecin = G[nod][i];
if(!vizitat[vecin])
DFS(vecin);
}
S.push(nod);
}
void DFSt(int nod)
{
vizitat[nod] = 2;
CTC[nrCTC].push_back(nod);
for(unsigned int i=0; i<GT[nod].size();i++) {
int vecin = GT[nod][i];
if(vizitat[vecin]==1)
DFSt(vecin);
}
}
void Kosaraju()
{
for(int i=1;i<=n;i++)
if(!vizitat[i])
DFS(i);
while(!S.empty()) {
int nod = S.top();
cout << nod << " ";
if (vizitat[nod] == 1) {
nrCTC++;
DFSt(nod);
}
S.pop();
}
}
void Print()
{
fout << nrCTC <<"\n";
for(int i = 1; i <= nrCTC; i++) {
for(unsigned int j = 0; j < CTC[i].size(); j++)
fout << CTC[i][j] <<" ";
fout<<"\n";
}
}
int main()
{
Read();
Kosaraju();
Print();
return 0;
}