Pagini recente » Cod sursa (job #2961344) | Cod sursa (job #3317203) | Profil Mar1vs | Monitorul de evaluare | Cod sursa (job #3343391)
#include <fstream>
#include <stack>
#include <vector>
#include <set>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 1e5 + 1;
int n, m, timp, nrCtc;
bool inSt[NMAX];
int d[NMAX], nma[NMAX];
vector<int> G[NMAX], CTC[NMAX];
stack<int> st;
void citire() {
int x, y;
fin >> n >> m;
while(m--) {
fin >> x >> y;
G[x].push_back(y);
}
}
void dfs(int x) {
d[x] = ++timp;
nma[x] = d[x];
st.push(x);
inSt[x] = 1;
for(const auto& y : G[x]) {
if(d[y] == 0) {
dfs(y);
nma[x] = min(nma[x], nma[y]);
} else if(inSt[y]) {
nma[x] = min(nma[x], d[y]);
}
}
if(d[x] == nma[x]) {
int y;
++nrCtc;
do {
y = st.top();
st.pop();
CTC[nrCtc].push_back(y);
inSt[y] = 0;
} while(y != x);
}
}
void afisare() {
fout << nrCtc << '\n';
for(int i = 1; i <= nrCtc; ++i) {
for(const auto& x : CTC[i]) {
fout << x << ' ';
}
fout << '\n';
}
}
int main() {
citire();
for(int i = 1; i <= n; ++i) {
if(d[i] == 0) {
dfs(i);
}
}
afisare();
return 0;
}