Pagini recente » Cod sursa (job #802518) | Cod sursa (job #316135) | Cod sursa (job #742071) | Borderou de evaluare (job #996835) | Cod sursa (job #2636559)
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sz() size()
#define fr first
#define sc second
#define int long long
#define mp make_pair
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;
const int nmax = 100005;
int n,m,_curr = -1;
vector<int>nod[nmax],nod_R[nmax],vecc,scc[nmax];
bitset<nmax>viz;
void DFS(int s){
viz[s] = 1;
for(auto it : nod[s]){
if(!viz[it]){
DFS(it);
}
}
vecc.push_back(s);
}
void DFS2(int s){
viz[s] = 1;
scc[_curr].push_back(s);
for(auto it : nod_R[s]){
if(!viz[it]){
DFS2(it);
}
}
}
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
srand(chrono::steady_clock::now().time_since_epoch().count());
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
cin >> n >> m;
for(int i=1;i<=m;i++){
int x,y;
cin >> x >> y;
nod[x].push_back(y);
nod_R[y].push_back(x);
}
for(int i=1;i<=n;i++){
if(!viz[i]) DFS(i);
}
viz.reset();
reverse(all(vecc));
for(auto it : vecc){
if(!viz[it]){
++_curr;
DFS2(it);
}
}
cout << (_curr + 1LL) << '\n';
for(int i=0;i<=_curr;i++){
for(auto it : scc[i]) cout << it << ' ';
cout << '\n';
}
}