Pagini recente » Cod sursa (job #2825527) | Cod sursa (job #2573008) | Cod sursa (job #1055054) | Cod sursa (job #2516142) | Cod sursa (job #3269142)
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream in ("ctc.in");
ofstream out ("ctc.out");
vector <int> adj[100002];
vector <int > r[100002];
int low[100002];
int id[100002];
int inS[100002];
int n;
int contor=1;
int m;
int k=0;
stack <int> s;
int viz[100002];
void dfs(int start){
viz[start]=1;
s.push(start);
inS[start]=1;
low[start]=++contor;
id[start]=contor;
for(int i=0;i<adj[start].size();i++){
int vecin=adj[start][i];
if(viz[vecin]==0)
dfs(vecin);
if(inS[vecin]==1){
low[start]=min(low[start],low[vecin]);
}
}
if(id[start]==low[start]){
while(s.top()!=start){
inS[s.top()]=0;
r[k].push_back(s.top());
s.pop();
}
inS[s.top()]=0;
r[k].push_back(s.top());
s.pop();
k++;
}
}
int main(){
in>>n>>m;
int x,y;
for(int i=1;i<=m;i++){
in>>x>>y;
adj[x].push_back(y);
}
for(int i=1;i<=n;i++){
if(viz[i]==0){
dfs(i);
}
}
out<<k<<'\n';
for(int i=0;i<k;i++){
for(int j=0;j<r[i].size();j++){
out<<r[i][j]<<" ";
}
out<<'\n';
}
return 0;
}