Pagini recente » Cod sursa (job #3336579) | Cod sursa (job #3347135) | Cod sursa (job #3350732) | Cod sursa (job #3326848) | Cod sursa (job #3342659)
#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
const int N=2e5+5;
vector<int> g[N];
int scc[N],tin[N],tout[N];
bool cyc[N];
int timer=0,comp=0;
stack<int> stk;
void dfs(int node)
{
tin[node]=tout[node]=++timer;
stk.push(node);
for(auto v:g[node])
{
if(!tin[v]) {dfs(v);tout[node]=min(tout[node],tout[v]);}
else if(!cyc[v]) tout[node]=min(tout[node],tout[v]);
}
if(tin[node]!=tout[node]) return;
++comp;
while(1)
{
int u=stk.top();
stk.pop();
cyc[u]=1,scc[u]=comp;
if(u==node) break;
}
}
signed main()
{
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n,m;
cin>>n>>m;
for(int _=1;_<=m;++_)
{
int u,v;cin>>u>>v;
g[u].pb(v);
}
for(int i=1;i<=n;++i)
{
if(!scc[i]) dfs(i);
}
vector<vector<int>> v(comp+5);
for(int i=1;i<=n;++i) v[scc[i]].pb(i);
cout<<comp<<'\n';
for(int i=1;i<=comp;++i)
{
for(auto x:v[i]) cout<<x<<" ";
cout<<'\n';
}
}