Pagini recente » Cod sursa (job #622232) | Cod sursa (job #1207070) | Cod sursa (job #2103237) | Cod sursa (job #2530056) | Cod sursa (job #2781279)
#include <bits/stdc++.h>
#include <fstream>
#define VMAX 100000
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> adj[VMAX];
stack <int> s;
int V, E, x, y, timp, nr_ctc, w;
bool onStack[VMAX];
int disc[VMAX], low[VMAX];
vector <int> ctc[VMAX];
void Tarjan(int u)
{
++timp;
disc[u] = timp;
low[u] = timp;
onStack[u] = true;
s.push(u);
for (auto w:adj[u])
{
if (!disc[w]) // elem. nou gasit, (u, v) tree edge
{
Tarjan(w);
// daca componenta aferenta lui v e mai "proaspata", atunci pot sa il bag si pe u in ea, ptc (u, v) e muchie deci pot accesa ac. ctc
low[u] = min(low[u], low[w]);
}
else if (onStack[w]) // daca este pe stack, atunci este unul dintre descendentii lui u
low[u] = min(low[u], disc[w]); // (ex geeksforgeeks) exista cazul in care w este "nodul de trecere" dintre o ctc si alta, deci low[w] ar indica eronat alta comp. conexa
else continue; // altfel, (u, v), este cross edge spre un CTC deja analizat, deci nu facem nimic
}
if (low[u] == disc[u]) // reprez. head node intr un SCC, adica nodul din SCC cu cel mai mic discovery time
{
while (s.top() != u) // cat timp nu ajung la head node
{
x = s.top();
ctc[nr_ctc].push_back(x);
onStack[x] = false;
s.pop();
}
x = s.top();
ctc[nr_ctc].push_back(x);
onStack[x] = false;
s.pop();
++nr_ctc;
}
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(0);
fout.tie(0);
fin >> V >> E;
while (E--)
{
fin >> x >> y;
adj[x - 1].push_back(y - 1);
}
for (int u = 0; u < V; ++u)
if (!disc[u]) Tarjan(u);
fout << nr_ctc << endl;
for (int i = 0; i < nr_ctc; ++i)
{
for (int j = 0; j < ctc[i].size(); ++j)
fout << ctc[i][j] + 1 << " ";
fout << endl;
}
fin.close();
fout.close();
return 0;
}