Cod sursa(job #771785)

Utilizator ionut_blesneagIonut Blesneag ionut_blesneag Data 27 iulie 2012 00:23:48
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#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;}