Pagini recente » Cod sursa (job #24428) | Cod sursa (job #664055) | Cod sursa (job #735894) | Cod sursa (job #2894629) | Cod sursa (job #1413535)
#include<stack>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
typedef struct lista
{
int info;
lista *next;
} * nod;
vector <int> ctc[100001];
stack <int> st;
nod a[100001];
nod b[100001];
bool viz[100001];
int nr,i,j,k,m,n,u;
void add(int x, nod &p)
{
nod r=new lista;
r->info=x;
r->next=p;
p=r;
}
void dfs1(int x)
{
viz[x]=1;
nod r=a[x];
while (r)
{
if (!viz[r->info]) dfs1(r->info);
r=r->next;
}
st.push(x);
}
void dfs2(int x)
{
viz[x]=0;
nod r=b[x];
while (r)
{
if (viz[r->info])
{
dfs2(r->info);
ctc[nr].push_back(r->info);
}
r=r->next;
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for (i=1; i<=m; ++i)
{
int x,y;
scanf("%d%d",&x,&y);
add(y,a[x]);
add(x,b[y]);
}
for (i=1; i<=n; ++i)
if (!viz[i]) dfs1(i);
while (st.size())
{
if (viz[st.top()]) ctc[++nr].push_back(st.top()),dfs2(st.top());
st.pop();
}
printf("%d\n",nr);
for (i=1; i<=nr; ++i) {
for (j=0; j<ctc[i].size(); ++j) printf("%d ",ctc[i][j]);
printf("\n");
}
return 0;
}