Pagini recente » Cod sursa (job #1429545) | Cod sursa (job #2614458) | Cod sursa (job #509232) | Cod sursa (job #1276259) | Cod sursa (job #2927040)
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
using namespace std;
int n, k=0;
vector<vector<int>> solutie;
ifstream f("ctc.in");
ofstream g("ctc.out");
struct vertex {
int index = -1;
int lowlink = -1;
bool peStiva = false;
};
void tareConex(int nod, int &ind, stack<int> &stiv, vertex v[n + 1], vector<vector<int>> &listaAdiacenta) {
v[nod].index = ind;
v[nod].lowlink = ind;
ind++;
stiv.push(nod);
v[nod].peStiva = true;
for (auto vec: listaAdiacenta[nod]) {
if (v[vec].index == -1) {
tareConex(vec, ind, stiv, v, listaAdiacenta);
v[nod].lowlink = min(v[nod].lowlink, v[vec].lowlink);
} else if (v[vec].peStiva)
v[nod].lowlink = min(v[nod].lowlink, v[vec].index);
}
if (v[nod].lowlink == v[nod].index) {
k++;
vector<int> sol;
int w;
do {
w = stiv.top();
stiv.pop();
v[w].peStiva = false;
sol.push_back(w);
}while(w!=nod);
solutie.push_back(sol);
}
}
void tarjan() {
int index = 0, m, x, y;
stack<int> stiva;
f >> n >> m;
vector<vector<int>> listaAd(n + 1);
for (int i = 0; i < m; i++) {
f >> x >> y;
listaAd[x].push_back(y);
}
f.close();
vertex v[n + 1];
for (int i = 1; i <= n; i++) {
if (v[i].index == -1)
tareConex(i, index, stiva, v, listaAd);
}
}
int main() {
tarjan();
g<<k<<"\n";
for(auto &it: solutie)
std::sort(it.begin(), it.end());
for(auto it: solutie)
{
for(auto nod: it)
g<<nod<<" ";
g<<"\n";
}
}