Pagini recente » Cod sursa (job #1546222) | Cod sursa (job #1276773) | Cod sursa (job #2147492) | Cod sursa (job #1006823) | Cod sursa (job #1232231)
#include<cstdio>
#include<vector>
#include<algorithm>
#define NMAX 100001
using namespace std;
int n,nr,m,i,x,y,k;
vector<int>v1[NMAX],v2[NMAX];
int viz1[NMAX],viz2[NMAX],sol[NMAX];
struct solutie
{
int nrcmp,ind;
}a[NMAX];
void DFS(int nod)
{
viz1[nod]=1;
vector<int>::iterator it;
for (it=v1[nod].begin();it!=v1[nod].end();++it)
{
if (viz1[*it]==0) DFS(*it);
}
sol[++k]=nod;
}
void DF(int nod)
{
viz2[nod]=1;
a[nod].ind=nod;
a[nod].nrcmp=nr;
vector<int>::iterator it;
for (it=v2[nod].begin();it!=v2[nod].end();++it)
{
if (viz2[*it]==0) DF(*it);
}
}
int cmp(solutie r,solutie p)
{
if (r.nrcmp>p.nrcmp) return 0;
else if (r.nrcmp==p.nrcmp && r.ind>p.ind) return 0;
else return 1;
}
void sortaret()
{
for (int i=1;i<=n;++i)
{
if (viz1[i]==0) DFS(i);
}
}
void ctc()
{
nr=0;
for (int i=k;i>=1;--i)
{
if (viz2[sol[i]]==0) DF(sol[i]),++nr;
}
sort(a+1,a+n+1,cmp);
}
void afis()
{
printf("%d\n",nr);
a[0].nrcmp=a[1].nrcmp;
for (i=1;i<=n;++i)
{
if (a[i].nrcmp!=a[i-1].nrcmp) printf("\n%d ",a[i].ind);
else printf("%d ",a[i].ind);
}
}
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);
v1[x].push_back(y);
v2[y].push_back(x);
}
sortaret();
ctc();
afis();
return 0;
}