Pagini recente » Profil Diana-Elena | Cod sursa (job #2114521) | Cod sursa (job #1704903) | Borderou de evaluare (job #2259295) | Cod sursa (job #2984521)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int NMax = 100005;
vector<int> v[NMax],c[NMax],con;
bool instiva[NMax];
int lowlink[NMax], idx[NMax],com[NMax];
int n, m,indecs,nrctc;
stack<int> s;
void tarjan(int nod) {
idx[nod] = lowlink[nod] = indecs;
indecs++;
s.push(nod);
instiva[nod] = true;
for (unsigned i = 0; i < v[nod].size(); i++) {
int vecin = v[nod][i];
if (idx[vecin] == -1) {
tarjan(vecin);
lowlink[nod] = min(lowlink[nod], lowlink[vecin]);
}
else {
if (instiva[vecin]) {
lowlink[nod] = min(lowlink[nod], lowlink[vecin]);
}
}
}
if (idx[nod] == lowlink[nod]) {
nrctc++;
int newnod;
do {
newnod = s.top();
c[nrctc].push_back(newnod);
s.pop();
instiva[newnod] = false;
} while (newnod != nod);
}
}
int main() {
f>> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
f >> x >> y;
v[x].push_back(y);
}
for (int i = 1; i <= n; i++) {
idx[i] = -1;
}
for (int i = 1; i <= n; i++) {
if (idx[i] == -1) {
tarjan(i);
}
}
g << nrctc<<'\n';
for (int i = nrctc; i >= 1;--i) {
for (unsigned j = 0; j < c[i].size(); j++) {
g << c[i][j] << ' ';
}
g << '\n';
}
}