Pagini recente » Cod sursa (job #16669) | Cod sursa (job #68747) | Cod sursa (job #1801462) | Cod sursa (job #491821) | Cod sursa (job #2703293)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in"); ofstream g("ctc.out");
stack <int> S;
vector <int> G[100005],GT[100005],CTC[100005];
int N, M, NrCTC, viz[100005];
void citire()
{ f>>N>>M;
for(int i=1; i<=M; ++i)
{ int x, y;
f>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
}
void DFSP(int Nod)
{ viz[Nod]=1;
for(unsigned int i=0; i<G[Nod].size(); ++i)
{ int Vecin=G[Nod][i];
if(!viz[Vecin]) DFSP(Vecin);
}
S.push(Nod);
}
void DFSM(int Nod)
{ viz[Nod]=2;
CTC[NrCTC].push_back(Nod);
for(unsigned int i=0; i<GT[Nod].size(); ++i)
{ int Vecin=GT[Nod][i];
if(viz[Vecin]==1) DFSM(Vecin);
}
}
void rez()
{ for(int i=1; i<=N; ++i)
if(!viz[i]) DFSP(i);
while(!S.empty())
{ int Nod=S.top();
if(viz[Nod]==1)
{ NrCTC++;
DFSM(Nod);
}
S.pop();
}
}
void scriere()
{ g<<NrCTC<<'\n';
for(int i=1; i<=NrCTC; ++i)
{ for(unsigned int j=0; j<CTC[i].size(); ++j) g<<CTC[i][j]<<' ';
g<<'\n';
}
}
int main()
{ citire();
rez();
scriere();
f.close(); g.close(); return 0;
}