Pagini recente » Cod sursa (job #1581422) | Cod sursa (job #3200695) | Cod sursa (job #3278805) | Cod sursa (job #1913558) | Cod sursa (job #1460587)
#include <stdio.h>
#include <vector>
#include <cstring>
#include <stack>
#include <bitset>
#define nmax 100010
using namespace std;
int n,m,i,j,x,y,nr,fr[nmax];
vector <int> g[nmax],gt[nmax],sol[nmax];
stack <int> st;
void dfs(int x)
{
int i; fr[x]=1;
for (i=0;i<g[x].size();i++)
if (fr[g[x][i]]==0) dfs(g[x][i]);
st.push(x);
}
void dfss(int x)
{
int i; fr[x]=1; sol[nr].push_back(x);
for (i=0;i<gt[x].size();i++)
if (fr[gt[x][i]]==0) dfss(gt[x][i]);
}
int main(){
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&n,&m);
for (i=1;i<=m;i++) {
scanf("%d %d",&x,&y);
g[x].push_back(y);
gt[y].push_back(x);
}
for (i=1;i<=n;i++)
if (fr[i]==0) dfs(i);
memset(fr,0,sizeof(fr));
while (!st.empty()) {
if (fr[st.top()]==0) nr++,dfss(st.top());
st.pop();
}
printf("%d\n",nr);
for (i=1;i<=nr;i++) {
for (j=0;j<sol[i].size();j++) printf("%d ",sol[i][j]);
printf("\n");
}
return 0;
}