Pagini recente » Cod sursa (job #2580119) | Cod sursa (job #126829) | Cod sursa (job #965651) | Cod sursa (job #2651725) | Cod sursa (job #2939838)
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
const int MAX_N = 100005;
int n, m, outcnt;
vector <int> out[MAX_N], v[MAX_N];
bitset <MAX_N> ctc, viz;
stack <int> stk;
int lvl, init[MAX_N], level[MAX_N];
inline void tarjan(int nod){
viz[nod] = true;
stk.push(nod);
level[nod] = init[nod] = ++lvl;
for(auto nxt : v[nod]){
if(!ctc[nxt]){
if(!viz[nxt]){
tarjan(nxt);
level[nod] = min(level[nod], level[nxt]);
}else{
level[nod] = min(level[nod], init[nxt]);
}
}
}
if(level[nod] == init[nod]){
outcnt++;
while(stk.top() != nod){
out[outcnt].emplace_back(stk.top());
stk.pop();
}
out[outcnt].emplace_back(stk.top());
stk.pop();
}
}
int main (){
ios_base::sync_with_stdio(false);
fin.tie(nullptr), fout.tie(nullptr);
fin>>n>>m;
for(int i=1, nod1, nod2; i<=m; i++){
fin>>nod1>>nod2;
v[nod1].emplace_back(nod2);
}
for(int i=1; i<=n; i++)
if(!viz[i])
tarjan(i);
fout<<outcnt<<"\n";
for(int i=1; i<=outcnt; i++, fout<<"\n")
for(auto nod : out[i])
fout<<nod<<" ";
return 0;
}