Pagini recente » Cod sursa (job #2712678) | Cod sursa (job #2443541) | Cod sursa (job #2356460) | Cod sursa (job #1350109) | Cod sursa (job #3268958)
//https://infoarena.ro/problema/ctc
#include <iostream>
#include <stack>
#include <vector>
#include <set>
using namespace std;
vector<int> g[1001], rg[1001];
int n;
stack<int> nodes, comp;
bool b[1001];
void dfs(int i, stack<int>& st,
const vector<int> graph[])
{
b[i]=true;
for (auto it:graph[i]){
if (!b[it]){
dfs(it, st, graph);
}
}
st.push(i);
}
vector<set<int>> sol;
void kosaraju(){
for (int i=1; i<=n; ++i){
if (!b[i])dfs(i, nodes, g);
}
fill(b, b+n+1, false);
while (!nodes.empty()){
int i=nodes.top();
nodes.pop();
if (!b[i]){
dfs(i, comp, rg);
sol.push_back({});
while (!comp.empty()){
sol.back().insert(comp.top());
comp.pop();
}
}
}
}
int main(){
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int m;
cin>>n>>m;
while (m--){
int x, y;
cin>>x>>y;
g[x].push_back(y);
rg[y].push_back(x);
//cout<<y<<" - "<<x<<endl;
}
kosaraju();
cout<<sol.size()<<endl;
for (auto it:sol){
for (auto jt:it){
cout<<jt<<" ";
}
cout<<"\n";
}
}