Pagini recente » Cod sursa (job #879169) | Cod sursa (job #1818790)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
const int N=100005;
int viz[N],viz2[N],cnt;
vector <int> G[N];
vector <int> T[N];
vector <int> Sol[N];
stack <int> st;
void dfs(int x){
viz[x]=1;
for(int i=0;i<(int)G[x].size();i++){
int y=G[x][i];
if(viz[y]==0) dfs(y);
}
st.push(x);
}
void dfs2(int x){
viz2[x]=1;
Sol[cnt].push_back(x);
for(int i=0;i<(int)T[x].size();i++){
int y=T[x][i];
if(viz2[y]==0) dfs2(y);
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int n,m,a,b,i,j,x;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d%d",&a,&b);
G[a].push_back(b);
T[b].push_back(a);
}
for(i=1;i<=n;i++)
if(viz[i]==0) dfs(i);
while(!st.empty()){
x=st.top();
st.pop();
if(viz2[x]==1) continue;
cnt++;
dfs2(x);
}
printf("%d\n",cnt);
for(i=1;i<=cnt;i++){
for(j=0;j<(int)Sol[i].size();j++){
printf("%d ",Sol[i][j]);
}
printf("\n");
}
return 0;
}