Pagini recente » Cod sursa (job #3165503) | Cod sursa (job #2155096) | Cod sursa (job #2628685) | Cod sursa (job #1526919) | Cod sursa (job #2928443)
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
stack <int> stiva;
vector <bool> peStiva;
vector <int> lowlink, index;
int timp = 0, nrCtc = 0;
vector <vector<int>> lista_ad, componente;
void tareConexe(int nod) {
index[nod] = timp;
lowlink[nod] = timp;
timp += 1;
stiva.push(nod);
peStiva[nod] = true;
for(auto n: lista_ad[nod]) {
if (index[n] == -1) {
tareConexe(n);
lowlink[nod] = min(lowlink[nod], lowlink[n]);
}
else if(peStiva[n])
lowlink[nod] = min(lowlink[nod], index[n]);
}
if(lowlink[nod] == index[nod]) {
while(stiva.top() != nod) {
peStiva[stiva.top()] = false;
componente[nrCtc].push_back(stiva.top());
stiva.pop();
}
componente[nrCtc].push_back(stiva.top());
nrCtc++;
peStiva[stiva.top()] = false;
stiva.pop();
}
}
int main() {
int n, m;
f >> n >> m;
lista_ad.resize(n + 1);
index.resize(n + 1, -1);
lowlink.resize(n + 1, -1);
peStiva.resize(n + 1, false);
componente.resize(m);
for(int i = 1; i <= m; i++) {
int a, b;
f >> a >> b;
lista_ad[a].push_back(b);
}
// for(int i = 1; i <= n; i++) {
// cout << i << " : ";
// for(int j = 0; j < lista_ad[i].size(); j++)
// cout << lista_ad[i][j] << " ";
// cout << endl;
// }
for(int i = 1; i <= n; i++)
if(index[i] == -1) {
tareConexe(i);
}
g << nrCtc << "\n";
for(int i = 0; i < nrCtc; i++) {
for(int j = 0; j < componente[i].size(); j++)
g << componente[i][j] << " ";
g << "\n";
}
return 0;
}