Pagini recente » Cod sursa (job #2229518) | Cod sursa (job #1731033) | Cod sursa (job #1730314) | Cod sursa (job #1636372) | Cod sursa (job #1365575)
#include<fstream>
using namespace std;
int n,m,i,viz1[100002],viz2[100002],c,viz[100002],x,y,j;
struct nodd
{
int x;
nodd *leg;
};
nodd *q,*av[100002];
struct nod
{
int x;
nod *leg;
};
nod *p,*v[100002],*t[100002];
void dfs(int x)
{
nod *p;
viz1[x]=1;
for(p=v[x];p!=0;p=p->leg)
{
if(viz1[p->x]==0 && viz[q->x]==0)
{
dfs(p->x);
}
}
}
void adfs(int x)
{
nodd *q;
viz2[x]=1;
for(q=av[x];q!=0;q=q->leg)
{
if(viz2[q->x]==0 && viz[q->x]==0)
{
adfs(q->x);
}
}
}
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>x>>y;
p=new nod;
p->x=y;
p->leg=v[x];
v[x]=p;
q=new nodd;
q->x=x;
q->leg=av[y];
av[y]=q;
}
c=0;
for(i=1;i<=n;i++)
{
if(viz[i]==0)
{
c++;
for(j=1;j<=n;j++)
{
viz1[j]=0;
viz2[j]=0;
}
dfs(i);
adfs(i);
for(j=i;j<=n;j++)
{
if(viz1[j]==1 && viz2[j]==1 && viz[j]==0)
{
viz[j]=1;
//fout<<j<<" ";
p=new nod;
p->x=j;
p->leg=t[c];
t[c]=p;
}
else
{
if(viz[j]==0)
{
viz1[j]=0;
viz2[j]=0;
}
}
}
//fout<<"\n";
}
}
fout<<c<<"\n";
for(i=1;i<=c;i++)
{
for(p=t[i];p!=0;p=p->leg)
{
fout<<p->x<<" ";
}
fout<<"\n";
}
fin.close();
fout.close();
return 0;
}