Pagini recente » Cod sursa (job #23139) | Cod sursa (job #1349973) | Cod sursa (job #1269279) | Cod sursa (job #1354136) | Cod sursa (job #3269092)
#include <iostream>
#include <stack>
#include <vector>
#include <set>
#include <map>
using namespace std;
stack<int> nodes;
int n, m, b[100001];
bool instack[100001];
vector<int> g[100001];
vector<set<int>> sol;
void dfs(int i){
//cout<<i<<" - "<<m<<endl;
b[i]=++m;
int org=m;
nodes.push(i);
instack[i]=true;
for (auto it:g[i]){
if (!b[it]){
dfs(it);
}
if (instack[it]){
b[i]=min(b[i], b[it]);
}
}
if (b[i]==org){
sol.push_back({});
while (!nodes.empty()){
sol.back().insert(nodes.top());
instack[nodes.top()]=false;
if (nodes.top()==i){
nodes.pop();
break;
} else {
nodes.pop();
}
}
}
}
int main(){
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
cin>>n>>m;
while (m--){
int x, y;
cin>>x>>y;
g[x].push_back(y);
}
m=0;
for (int i=1; i<=n; ++i){
if (!b[i]){
dfs(i);
}
}
cout<<sol.size()<<"\n";
for (auto it:sol){
for (auto jt:it){
cout<<jt<<" ";
}
cout<<"\n";
}
}