Pagini recente » Cod sursa (job #2670074) | Cod sursa (job #220067) | Cod sursa (job #2117527) | Cod sursa (job #738006) | Cod sursa (job #771785)
Cod sursa(job #771785)
#include<fstream>
using namespace std;
int n,m,i,j;
struct lista
{int nod;
lista* next;};
lista* a[100001];
lista* b[100001];
void addplus(int x, int y)
{lista* q = new lista;
q->nod=y;
q->next=a[x];
a[x]=q;}
void addminus(int x, int y)
{lista* q = new lista;
q->nod=y;
q->next=b[x];
b[x]=q;}
ifstream f("ctc.in");
ofstream g("ctc.out");
int vizplus[100001], vizminus[100001], nrconex, viz[100001];
void depthplus(int e)
{lista* q=a[e];
while(q)
{if(vizplus[q->nod]==0)
{vizplus[q->nod]=nrconex;
depthplus(q->nod);}
q=q->next;}
}
void depthminus(int e)
{lista* q=b[e];
while(q)
{if(vizminus[q->nod]==0 && vizplus[q->nod]==nrconex)
{vizminus[q->nod]=nrconex;
depthminus(q->nod);}
q=q->next;}
}
int main()
{f>>n>>m;
int x,y;
for( i=1; i<=m; i++)
{f>>x>>y;
addplus(x,y);
addminus(y,x);}
for(i=1; i<=n; i++)
{if(vizminus[i]==0) // || vizplus[j]!=vizminus[j])
{nrconex++;
vizplus[i]=nrconex;
vizminus[i]=nrconex;
depthplus(i);
depthminus(i);
/*for(j=1; j<=n; j++)
if(vizplus[j]!=vizminus[j])
vizplus[j]=vizminus[j]=0; */}
}
/*for(i=1; i<=n; i++)
g<<vizplus[i]<<" ";
g<<endl;
for(i=1; i<=n; i++)
g<<vizminus[i]<<" "; */
g<<nrconex<<endl;
for(i=1; i<=nrconex; i++)
{for(j=1; j<=n; j++)
if(vizplus[j]==i)
g<<j<<" ";
g<<endl;}
f.close();
g.close();
return 0;}