Pagini recente » Istoria paginii utilizator/colt2005 | Cod sursa (job #2013857) | Cod sursa (job #1321546) | Cod sursa (job #2916096) | Cod sursa (job #3295940)
#include<bits/stdc++.h>
using namespace std;
string numeFisier="ctc";
ifstream fin(numeFisier+".in"); ofstream fout(numeFisier+".out");
#define cin fin
#define cout fout
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
//#define int ll
int n,m;
vector<int> g[100010];
vector<int> component[100010];
int indexArray0=0;
int indexArray[100010];
int lowlink[100010];
bool onStack[100010];
stack<int> st;
void strongConnected(int u){
indexArray0++;
indexArray[u] =indexArray0;
lowlink[u] = indexArray0;
st.push(u);
onStack[u]=true;
for(int v:g[u]){
if(!indexArray[v]){
strongConnected(v);
lowlink[u]=min(lowlink[u], lowlink[v]);
}
else{
if( onStack[v] ){
lowlink[u] = min(lowlink[u], indexArray[v]);
}
}
}
if( lowlink[u]==indexArray[u] ){
while(!st.empty() && st.top()!=u ){
onStack[u]=false;
component[u].pb(st.top());
st.pop();
}
component[u].pb(u);
st.pop();
}
}
int32_t main(){
INIT
cin>>n>>m;
for(int i=1,x,y; i<=m; i++){
cin>>x>>y;
g[x].pb(y);
}
for(int i=1; i<=n; i++){
if(!indexArray[i]){
strongConnected(i);
}
}
int cnt = 0;
for(int i=1; i<=n; i++){
if(component[i].size()>0){
cnt++;
}
}
cout<<cnt<<"\n";
for(int i=1; i<=n; i++){
if(component[i].size()>0){
for(int x:component[i]){
cout<<x<<" ";
}
cout<<"\n";
}
}
return 0;
}