Pagini recente » Cod sursa (job #1266256) | Cod sursa (job #1291974) | Cod sursa (job #2636758) | Cod sursa (job #1131482) | Cod sursa (job #2931219)
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
const int MAX_N = 100005;
const int MAX_M = 200005;
int n, m, outcnt;
vector <int> edge[MAX_N], output[MAX_N];
bitset <MAX_N> viz, ctc;
stack <int> stk;
static inline void add_ctc(){
ctc[stk.top()] = true;
output[outcnt].emplace_back(stk.top());
stk.pop();
}
int level[MAX_N], init[MAX_N], lvl;
inline void tarjan(int crt){
viz[crt] = true;
stk.push(crt);
level[crt] = init[crt] = ++lvl;
for(auto nxt : edge[crt])
if(!ctc[nxt]){
if(!viz[nxt]){
tarjan(nxt);
level[crt] = min(level[crt], level[nxt]);
}else{
level[crt] = min(level[crt], init[nxt]);
}
}
if(level[crt] == init[crt]){
outcnt++;
while(stk.top() != crt)
add_ctc();
add_ctc();
}
}
int main (){
ios_base::sync_with_stdio(false);
fin.tie(nullptr);
fout.tie(nullptr);
fin>>n>>m;
for(int i=1; i<=m; i++){
int u, v;
fin>>u>>v;
edge[u].emplace_back(v);
}
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 : output[i])
fout<<nod<<" ";
return 0;
}