Pagini recente » Cod sursa (job #776028) | Cod sursa (job #1298859) | Cod sursa (job #1183828) | Cod sursa (job #1414752) | Cod sursa (job #1790489)
#include <fstream>
#include <vector>
using namespace std;
struct Nod
{
int timp = 0;
int timp_minim = 0;
bool in_stiva;
vector<int> vecini;
};
typedef vector<Nod> Graf;
int TIMP = 0;
void Tarjan(Graf &g, int start, vector<int> &st, vector<vector<int>> &ctc)
{
g[start].timp = g[start].timp_minim = ++TIMP;
st.push_back(start);
g[start].in_stiva = true;
for (int vecin : g[start].vecini) {
if (g[vecin].timp == 0)
Tarjan(g, vecin, st, ctc);
if (g[vecin].in_stiva)
g[start].timp_minim = min(g[start].timp_minim, g[vecin].timp_minim);
}
if (g[start].timp_minim == g[start].timp) {
vector<int> comp;
do {
comp.push_back(st.back());
g[st.back()].in_stiva = false;
st.pop_back();
} while (comp.back() != start);
ctc.push_back(comp);
}
}
vector<vector<int>> AflaCTC(Graf &g)
{
vector<vector<int>> componente;
for (unsigned i = 1; i < g.size(); ++i) {
if (g[i].timp == 0) {
vector<int> stiva;
Tarjan(g, i, stiva, componente);
}
}
return componente;
}
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
fin >> n >> m;
Graf graf(n + 1);
while (m--) {
int x, y;
fin >> x >> y;
graf[x].vecini.push_back(y);
}
auto componente = AflaCTC(graf);
fout << componente.size() << "\n";
for (auto &comp : componente) {
for (int nod : comp)
fout << nod << " ";
fout << "\n";
}
return 0;
}