Pagini recente » Documentatie | Cod sursa (job #3294773) | Scrie articole | Cod sursa (job #965518) | Cod sursa (job #3294828)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in ("cct.in");
ofstream out ("cct.out");
stack <int> s;
int low_link[100002];
int id[100002];
int viz[100002];
int on_stack[100002];
int cct=1;
int n,m;
int idem;
vector <int> adj[100002];
vector <int> rez[100002];
void dfs(int nod){
id[nod]=++idem;
low_link[nod]=idem;
s.push(nod);
on_stack[nod]=1;
viz[nod]=1;
for(auto neighboar : adj[nod]){
if(viz[neighboar]==0){
dfs(neighboar);
}
if(on_stack[neighboar]==1){
low_link[nod]=min(low_link[nod],low_link[neighboar]);
}
}
if(id[nod]==low_link[nod]){
while(true){
int top=s.top();
on_stack[s.top()]=0;
rez[cct].push_back(s.top());
s.pop();
if(top==nod)
break;
}
cct++;
}
}
int main(){
in>>n>>m;
for(int i=1;i<=m;i++){
int a,b;
in>>a>>b;
adj[a].push_back(b);
//adj[b].push_back(a);
}
for(int i=1;i<=n;i++){
if(viz[i]==0){
dfs(i);
}
}
out<<cct-1<<'\n';
for(int i=1;i<cct;i++){
for( auto it : rez[i]){
out<<it<<" ";
}
out<<'\n';
}
return 0;
}