Pagini recente » Cod sursa (job #2136138) | Cod sursa (job #2826077) | Cod sursa (job #2865913) | Cod sursa (job #2455679) | Cod sursa (job #1261757)
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int N=100000;
vector<int>g[N+1],h[N+1],ctc[N+1];
queue<int>q;
stack<int>st;
bool vis[N+1];
int n,m;
void dfs(int dad){
vis[dad]=true;
for(int i=0;i<g[dad].size();i++){
int son=g[dad][i];
if(!vis[son])
dfs(son);
}
st.push(dad);
}
void bfs(int node,int k){
q.push(node);
vis[node]=true;
while(!q.empty()){
int dad=q.front();
for(int i=0;i<h[dad].size();i++){
int son=h[dad][i];
if(!vis[son]){
vis[son]=true;
q.push(son);
}
}
ctc[k].push_back(dad);
q.pop();
}
}
int main(){
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
g[x].push_back(y);
h[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(!vis[i])
dfs(i);
int res=0;
memset(vis,0,sizeof(vis));
while(!st.empty()){
if(!vis[st.top()])
bfs(st.top(),++res);
st.pop();
}
printf("%d\n",res);
for(int i=1;i<=res;i++){
for(int j=0;j<ctc[i].size();j++)
printf("%d ",ctc[i][j]);
printf("\n");
}
return 0;
}