Pagini recente » Cod sursa (job #2742183) | Cod sursa (job #3121075) | Cod sursa (job #2301669) | Cod sursa (job #434182) | Cod sursa (job #3300454)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
// #include <bits/stdc++.h>
#define in fin
#define out fout
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> g[100001];
int h[100001], niv[100001];
stack<int> st;
int m[100001];
vector< vector<int> > ctc;
int it = 1;
void dfs(int nod){
st.push(nod);
m[nod] = 2;
for(const int &x : g[nod]){
if(m[x] == 2){
h[nod] = min(h[nod], niv[x]);
continue;
}
if(m[x]) continue; // transversala skibidi dinaia
niv[x] = h[x] = ++it;
dfs(x);
h[nod] = min(h[nod], h[x]);
}
if(h[nod] >= niv[nod]){ // e comp
// cout << nod << " e 'cap' de componenta\n";
ctc.push_back({});
while(st.top() != nod){
ctc.back().push_back(st.top());
st.pop();
}
ctc.back().push_back(st.top()); st.pop();
m[nod] = 1;
}
}
signed main(){
ios_base::sync_with_stdio(false);
in.tie(NULL);
int n, M; in >> n >> M;
for(int i = 0; i < M; i++){
int a, b; in >> a >> b;
g[a].push_back(b);
}
for(int i = 1; i <= n; i++){
if(!m[i]) dfs(i);
}
out << ctc.size() << '\n';
for(const vector<int> &x : ctc){
for(const int &y : x) out << y << " ";
out << '\n';
}
return 0;
}