Pagini recente » Cod sursa (job #869476) | Cod sursa (job #1074667) | Cod sursa (job #1691381) | Cod sursa (job #1318382) | Cod sursa (job #2223594)
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int NMAX=100005;
vector <int> G[NMAX];
vector <int> GT[NMAX];
vector <int> sol[NMAX];
vector <int> viz;
stack <int> st;
int cc=0;
void dfs1(int u){
viz[u]=1;
for(int i=0;i<G[u].size(); ++i){
int v=G[u][i];
if(viz[v]==0)
dfs1(v);
}
st.push(u);
}
void dfs2(int u){
viz[u]=1;
for(int i=0;i<GT[u].size(); ++i){
int v=GT[u][i];
if(viz[v]==0)
dfs2(v);
}
sol[cc].push_back(u);
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int n,m;
int u,v;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%d%d",&u,&v);
G[u].push_back(v);
GT[v].push_back(u);
}
viz.assign(n+1,0);
for(int i=1;i<=n;++i)
if(viz[i]==0)
dfs1(i);
viz.clear();
viz.assign(n+1,0);
while(!st.empty()){
if(viz[st.top()]==0){
++cc;
dfs2(st.top());
}
st.pop();
}
printf("%d\n",cc);
for(int i=1;i<=cc;++i){
for(int j=0; j<sol[i].size();++j)
printf("%d ",sol[i][j]);
printf("\n");
}
return 0;
}