Pagini recente » Cod sursa (job #2369303) | Cod sursa (job #3159450) | Cod sursa (job #2705670) | Cod sursa (job #1638304) | Cod sursa (job #2958669)
/* Componentele tare-conexe (G.O.)
* Algoritmul lui Tarjan
* Complexitate:
*
* O(m) ca timp de executare
* O(m) ca spatiu de memorie ocupat
*/
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
using VI = vector<int>;
using VVI = vector<VI>;
using VB = vector<bool>;
VVI G;
VB v; // marcam nodurile vizitate
VB inStack; // marcam nodurile din stiva
VVI ctc; // retine pe fiecare linie cate o comp tare conexa
VI c; // comp tare conexa curenta
stack<int> stk; // retine nodurile in ordinea descoperirii acestora
VI index, low; // indexul si indexul minim pt fiecare nod
int idx;
int n, m;
void CitesteGraf();
void Tarjan();
void Df(int x);
void ScrieCTC();
int main()
{
CitesteGraf();
Tarjan();
ScrieCTC();
return 0;
}
void Tarjan()
{
for (int node = 1; node <= n; ++node)
if (!v[node])
Df(node);
}
void Df(int x)
{
v[x] = true;
index[x] = low[x] = ++idx;
stk.push(x);
inStack[x] = true;
for (int const& y : G[x])
if (!v[y]) // y este fiul lui x
{
Df(y);
low[x] = min(low[x], low[y]);
}
else // daca
if (inStack[y]) // daca y este stramos al lui x (adica x->y = muchie de intoarcere)
low[x] = min(low[x], index[y]);
if (index[x] == low[x]) // x este repreentanul unei noi comp. t-c
{
c.clear();
while (!stk.empty())
{
int node = stk.top();
stk.pop();
inStack[node] = false;
c.push_back(node);
if (node == x)
break;
}
ctc.push_back(c);
}
}
void CitesteGraf()
{
fin >> n >> m;
G = VVI(n + 1);
v = VB(n + 1);
index = low = VI(n + 1);
inStack = VB(n + 1);
int x, y;
while (m--)
{
fin >> x >> y;
G[x].push_back(y);
}
}
void ScrieCTC()
{
fout << ctc.size() << '\n';
for (auto const&C : ctc)
{
for (const int& node : C)
fout << node << ' ';
fout << '\n';
}
}