Pagini recente » Cod sursa (job #243168) | Cod sursa (job #933526) | Cod sursa (job #2103816) | Cod sursa (job #1754514) | Cod sursa (job #2175528)
#include<fstream>
#include<list>
#include<bitset>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int Nmax = 100005;
list<int>Graf[Nmax], GrafT[Nmax], Sol[Nmax];
bitset<Nmax>Viz;
int Topologic[Nmax], NrElemTopologic, NrCompTC, NrNoduri, NrMuchii;
void Citire(){
f >> NrNoduri >> NrMuchii;
int nod1, nod2;
for(int Index = 1; Index <= NrMuchii; ++Index){
f >> nod1 >> nod2;
Graf[nod1].push_back(nod2);
GrafT[nod2].push_back(nod1);
}
}
void SortareTopologica(int NodCurent){
list<int>::iterator it;
Viz[NodCurent] = true;
for(it = Graf[NodCurent].begin(); it != Graf[NodCurent].end(); ++it)
if(!Viz[*it])
SortareTopologica(*it);
Topologic[++NrElemTopologic] = NodCurent;
}
void ObtinereVectorSortTop(){
int Index;
for(Index = 1; Index <= NrNoduri; ++Index)
if(!Viz[Index])
SortareTopologica(Index);
}
void DFS(int NodCurent){
list<int>::iterator it;
Viz[NodCurent] = false;
Sol[NrCompTC].push_back(NodCurent);
for(it = GrafT[NodCurent].begin(); it != GrafT[NodCurent].end(); ++it)
if(Viz[*it])
DFS(*it);
}
void ObtinereCompTareConexe(){
int Index;
for(Index = NrElemTopologic; Index >= 1; --Index){
if(Viz[Topologic[Index]]){
++NrCompTC;
DFS(Topologic[Index]);
}
}
}
void Print(){
g << NrCompTC << '\n';
int Index;
list<int>::iterator it;
for(Index = 1; Index <= NrCompTC; ++Index){
for(it = Sol[Index].begin(); it != Sol[Index].end(); ++it)
g << *it << ' ';
g << '\n';
}
}
int main(){
Citire();
ObtinereVectorSortTop();
ObtinereCompTareConexe();
Print();
return 0;
}