Pagini recente » Cod sursa (job #1929608) | Cod sursa (job #621615) | Cod sursa (job #2678967) | Cod sursa (job #910123) | Cod sursa (job #633962)
Cod sursa(job #633962)
#include <cstdio>
#include <list>
#include <stack>
using namespace std;
const int MAX_N = 100005;
int n,m;
bool v[MAX_N];
list<int> l[MAX_N];
list<int> lt[MAX_N];
int st[MAX_N],nst;
list<int> ctc[MAX_N];
int nrCtc;
void DF1(int nod)
{
v[nod] = true;
list<int>::iterator it;
for(it = l[nod].begin(); it != l[nod].end(); ++it)
if(v[*it] == false)
DF1(*it);
st[++nst] = nod;
}
void DF2(int nod)
{
v[nod] = true;
list<int>::iterator it;
ctc[nrCtc].push_back(nod);
for(it = lt[nod].begin(); it != lt[nod].end(); ++it)
if(v[*it] == false)
DF2(*it);
}
int main()
{
FILE* fp;
int i,x,y,abc;
fp = freopen("ctc.in","rt",stdin);
fp = freopen("ctc.out","wt",stdout);
abc = scanf("%d %d",&n,&m);
for(i=1;i<=m;++i)
{
abc = scanf("%d %d",&x,&y);
l[x].push_back(y);
lt[y].push_back(x);
}
nrCtc = 0;
for(i=1;i<=n;i++)
if(v[i]==false)
DF1(i);
for(i=1;i<=n;i++)
v[i]=false;
for(i=n;i>=1;i--)
if(v[st[i]]==false)
{
nrCtc++;
DF2(st[i]);
}
printf("%d\n",nrCtc);
list<int>::iterator it;
for(i=1;i<=nrCtc;i++)
{
for(it = ctc[i].begin(); it != ctc[i].end(); ++it)
printf("%d ",*it);
printf("\n");
}
return 0;
}