Pagini recente » Cod sursa (job #1571970) | Cod sursa (job #2124619) | Cod sursa (job #1334168) | Cod sursa (job #813939) | Cod sursa (job #1895081)
#include<fstream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
struct nod
{
int v;
nod *adr;
};
int n,m,i,j,viz[200002],viz1[200002],viz2[200002],c,x,y;
nod *L1[100001], *L2[100001], *p;
void dfs(nod *L[],int vf, int v[])
{
int st[100001],k;
nod *p;
k=1;
st[k]=vf;
v[vf]=1;
while(k>0)
{
for(p=L[st[k]];p!=0;p=p->adr)
{
if(v[p->v]==0)
break;
}
if(p==0)
k--;
else
{
v[p->v]=1;
k++;
st[k]=p->v;
}
}
}
int main()
{
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
p=new nod;
p->v=y;
p->adr=L1[x];
L1[x]=p;
p=new nod;
p->v=x;
p->adr=L2[y];
L2[y]=p;
}
c=0;
for(i=1;i<=n;i++)
{
if(viz[i]==0)
{
c++;
dfs(L1,i,viz1);
dfs(L2,i,viz2);
for(j=1;j<=n;j++)
{
if(viz1[j]==1&&viz2[j]==1) viz[j]=c;
}
for(j=1;j<=n;j++)
{
viz1[j]=0;
viz2[j]=0;
}
}
}
g<<c<<'\n';
for(i=1;i<=c;i++)
{
for(j=1;j<=n;j++)
{
if(viz[j]==i) g<<j<<" ";
}
g<<'\n';
}
f.close();
g.close();
return 0;
}