Pagini recente » Cod sursa (job #2400451) | Cod sursa (job #2405832) | Cod sursa (job #1666632) | Cod sursa (job #1243454) | Cod sursa (job #1250413)
#include <cstdio>
#include <stack>
#include <vector>
#include <cstring>
using namespace std;
#define NMAX 100007
vector < int > G[NMAX],T[NMAX],C[NMAX];
bool marked[NMAX];
stack < int > S;
int i,N,X,Y,ctc,M,current;
void df_1(int node)
{
vector < int > :: iterator u;
for (u=G[node].begin();u!=G[node].end();++u)
{
if (marked[*u]) continue;
marked[*u]=true;
df_1(*u);
}
S.push(node);
}
void df_2(int node)
{
vector < int > :: iterator u;
for (u=T[node].begin();u!=T[node].end();++u)
{
if (marked[*u]) continue;
marked[*u]=true;
df_2(*u);
}
C[ctc].push_back(node);
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
for (scanf("%d%d",&N,&M);M;--M)
{
scanf("%d%d",&X,&Y);
G[X].push_back(Y);
T[Y].push_back(X);
}
for (i=1;i<=N;++i)
{
if (marked[i]) continue;
marked[i]=true;
df_1(i);
}
memset(marked,false,sizeof(marked));
while (!S.empty())
{
current=S.top();
S.pop();
if (marked[current]) continue;
++ctc;
marked[current]=true;
df_2(current);
}
for (printf("%d\n",ctc),i=1;i<=ctc;++i,printf("\n"))
for (vector < int > :: iterator u=C[i].begin();u!=C[i].end();++u)
printf("%d ",*u);
return 0;
}