Pagini recente » Istoria paginii utilizator/anamariapintilie | Cod sursa (job #335448) | Cod sursa (job #2256721) | Monitorul de evaluare | Cod sursa (job #1726384)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define NMAX 100000
struct Nod
{
int index;
int lowerBound;
bool vizitat;
bool inStiva;
vector<int> vecini;
};
Nod noduri[NMAX + 1];
vector<int> stiva;
vector< vector<int> > componente;
int timp = 0;
void tarjan(int nod);
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
fin >> n >> m;
while (m--) {
int x, y;
fin >> x >> y;
noduri[x].vecini.push_back(y);
}
for (int i = 1; i <= n; ++i) {
if (!noduri[i].vizitat) {
tarjan(i);
}
}
fout << componente.size() << "\n";
for (auto componenta : componente) {
for (int nod : componenta)
fout << nod << " ";
fout << "\n";
}
return 0;
}
void tarjan(int nod)
{
stiva.push_back(nod);
noduri[nod].inStiva = true;
noduri[nod].vizitat = true;
noduri[nod].index = noduri[nod].lowerBound = ++timp;
for (int vecin : noduri[nod].vecini) {
if (!noduri[vecin].vizitat)
tarjan(vecin);
if(noduri[vecin].inStiva)
noduri[nod].lowerBound = min(noduri[nod].lowerBound, noduri[vecin].lowerBound);
}
if (noduri[nod].lowerBound == noduri[nod].index) {
vector<int> componentaNoua;
do {
componentaNoua.push_back(stiva.back());
noduri[stiva.back()].inStiva = false;
stiva.pop_back();
} while (componentaNoua.back() != nod);
componente.push_back(componentaNoua);
}
}