Pagini recente » Cod sursa (job #2249400) | Cod sursa (job #2383689) | Cod sursa (job #2710349) | Cod sursa (job #1811022) | Cod sursa (job #1216709)
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
#define NMAX 200007
vector < int > G[NMAX],T[NMAX],C[NMAX];
bool sel[NMAX];
queue < int > Q;
int N,M,i,e,current,X,Y;
stack < int > S;
void df(int node)
{
vector < int > :: iterator i;
for (i=G[node].begin();i!=G[node].end();++i)
{
if (sel[*i]) continue;
sel[*i]=true;
df(*i);
}
S.push(node);
}
void specialdf(int start)
{
vector < int > :: iterator i;
int node;
Q.push(start);
sel[start]=true;
while (!Q.empty())
{
node=Q.front();
C[e].push_back(node);
for (i=T[node].begin();i!=T[node].end();++i)
{
if (sel[*i])
continue;
sel[*i]=true;
Q.push(*i);
}
Q.pop();
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&N,&M);
while (M--)
{
scanf("%d%d",&X,&Y);
G[X].push_back(Y);
T[Y].push_back(X);
}
for (i=1;i<=N;++i)
{
if (sel[i])
continue;
df(i);
}
memset(sel,false,sizeof(sel));
while (!S.empty())
{
current=S.top();
S.pop();
if (sel[current])
continue;
++e;
specialdf(current);
}
for (i=1,printf("%d\n",e);i<=e;++i,printf("\n"))
{
sort(C[i].begin(),C[i].end());
for (vector < int > :: iterator j=C[i].begin();j!=C[i].end();++j)
printf("%d ",*j);
}
return 0;
}