Pagini recente » Cod sursa (job #2223196) | Cod sursa (job #829220) | Cod sursa (job #1489112) | Monitorul de evaluare | Cod sursa (job #3310265)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
const int NMAX=1e5+5;
int n, m, t, ncc, viz[NMAX], dtime[NMAX], rtime[NMAX];
vector<int> adj[NMAX], scc[NMAX];
stack<int> st;
void DFS(int u)
{
viz[u]=1;
st.push(u);
dtime[u]=(t++);
rtime[u]=dtime[u];
for(auto v:adj[u])
{
if(viz[v]==0)
DFS(v);
if(viz[v]!=3)
rtime[u]=min(rtime[u], rtime[v]);
}
if(dtime[u]==rtime[u])
{
ncc++;
int c=0;
while(c!=u)
{
c=st.top(); st.pop();
scc[ncc].push_back(c);
viz[c]=3;
}
}
viz[u]=max(viz[u], 2);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a, b; cin>>a>>b;
adj[a].push_back(b);
}
for(int i=1;i<=n;i++)
if(viz[i]==0)
DFS(i);
cout<<ncc<<'\n';
for(int i=1;i<=ncc;i++, cout<<'\n')
for(auto u:scc[i])
cout<<u<<" ";
return 0;
}