Pagini recente » Cod sursa (job #1091893) | Cod sursa (job #3167411) | Cod sursa (job #2707875) | Cod sursa (job #497409) | Cod sursa (job #2795522)
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100001;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector <int> AdiacentaT[MAX];
vector <int> componente;
class Graf
{
int nrNoduri;
stack <int> Stiva;
bool Vizitat[MAX] = {0};
bool VizitatT[MAX] = {0};
public:
vector <int> Adiacenta[MAX];
Graf(int nrNoduri);
void UmpleStiva(int nod);
void Transpus();
void Parcurgere();
void DfsT(int nod);
void Ctc();
};
Graf :: Graf(int nrNoduri)
{
this->nrNoduri = nrNoduri;
}
void Graf :: Transpus()
{
for(int i = 1; i <= nrNoduri; ++i)
for(auto j : Adiacenta[i])
AdiacentaT[j].push_back(i);
}
void Graf :: UmpleStiva(int nod)
{
VizitatT[nod] = 1;
for(auto i : Adiacenta[nod])
if(!VizitatT[i])
UmpleStiva(i);
Stiva.push(nod);
}
void Graf :: Parcurgere()
{
for(int i = 1; i <= nrNoduri; ++i)
if(!VizitatT[i])
UmpleStiva(i);
}
void Graf :: DfsT(int nod)
{
Vizitat[nod] = 1;
componente.push_back(nod);
for(auto i : AdiacentaT[nod])
if(!Vizitat[i])
DfsT(i);
}
void Graf :: Ctc()
{
int total = 0;
while(!Stiva.empty())
{
int nod = Stiva.top();
Stiva.pop();
if(!Vizitat[nod])
{
total++;
DfsT(nod);
componente.push_back(-1);
}
}
out << total << endl;
for(int i = 0; i < componente.size(); i++)
if(componente[i] == -1)
out << endl;
else
out << componente[i] << " ";
}
int main()
{
int N, M;
in >> N >> M;
Graf g(N);
for(int i = 1; i <= M; ++i)
{
int nod1, nod2;
in >> nod1 >> nod2;
g.Adiacenta[nod1].push_back(nod2);
}
g.Transpus();
g.Parcurgere();
g.Ctc();
return 0;
}