Pagini recente » Cod sursa (job #2878176) | Cod sursa (job #1853909) | Cod sursa (job #2491124) | Cod sursa (job #373052) | Cod sursa (job #3278981)
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
void start() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cout << setprecision(12) << fixed;
srand(time(nullptr));
freopen("ctc.in", "r", stdin); freopen("ctc.out", "w", stdout);
}
int n, m;
vector<vector<int>> gr;
void read() {
cin>>n>>m;
gr.resize(n+1);
int a, b;
for (int i=0; i<m; i++){
cin>>a>>b;
gr[a].push_back(b);
}
}
int curr_idx = 0;
vector<int> idx;
vector<int> lowlink;
vector<bool> on_s;
vector<vector<int>> ans;
stack<int> s;
void tarjan(int node){
curr_idx ++;
idx[node] = curr_idx;
lowlink[node] = curr_idx;
s.push(node);
on_s[node] = true;
for (auto &x : gr[node]){
if (!on_s[x]){
// not visited
tarjan(x);
lowlink[node] = min(lowlink[node], lowlink[x]);
}
else if (on_s[x]){
// x in stack (otherwise it is part of another SCC (CTC) -> should be ignored)
lowlink[node] = min(lowlink[node], lowlink[x]);
}
}
if (idx[node] == lowlink[node]){
// node is the "root" of the SCC (CTC)
vector<int> curr_ans;
while (!s.empty()){
int w = s.top();
s.pop();
//on_s[w] = false;
curr_ans.push_back(w);
if (w == node){
break;
}
}
ans.push_back(curr_ans);
}
}
void solve() {
read();
idx.resize(n+1, 0);
lowlink.resize(n+1, 0);
on_s.resize(n+1, false);
for (int i=1; i<=n; i++){
if (!idx[i]){
curr_idx = 0;
tarjan(i);
}
}
cout<<ans.size()<<'\n';
for (auto &x : ans){
for (auto &y : x){
cout<<y<<" ";
}
cout<<'\n';
}
}
int main(){
start();
int t = 1;
// cin>>t;
for (int i=1; i<=t; i++){
solve();
}
return 0;
}