Pagini recente » Cod sursa (job #955244) | Cod sursa (job #1177606) | Cod sursa (job #2182073) | Cod sursa (job #477935) | Cod sursa (job #1254273)
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
const int N=100000;
const int M=200000;
vector<int>g[N+1];
vector<int>t[N+1];
vector<int>ctc[N+1];
queue<int>q;
stack<int>st;
bool stacked[N+1];
bool vis[N+1];
int k,n,m;
void bfs(int node){
ctc[++k].push_back(node);
q.push(node);
stacked[node]=false;
while(!q.empty()){
int dad=q.front();
for(int i=0;i<t[dad].size();i++){
int son=t[dad][i];
if(!vis[son]&&stacked[son]){
q.push(son);
ctc[k].push_back(son);
vis[son]=true;
stacked[son]=false;
}
}
q.pop();
}
}
void dfs(int dad){
for(int i=0;i<g[dad].size();i++){
int son=g[dad][i];
if(!vis[son]&&!stacked[son]){
vis[son]=true;
dfs(son);
}
}
st.push(dad);
stacked[dad]=true;
}
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);
t[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(!stacked[i]){
stacked[i]=true;
memset(vis,0,sizeof(vis));
dfs(i);
}
while(!st.empty()){
if(stacked[st.top()]){
memset(vis,0,sizeof(vis));
bfs(st.top());
}
st.pop();
}
printf("%d\n",k);
for(int i=1;i<=k;i++){
for(int j=0;j<ctc[i].size();j++)
printf("%d ",ctc[i][j]);
printf("\n");
}
return 0;
}