Cod sursa(job #2121744)

Utilizator monicalMonica L monical Data 4 februarie 2018 12:05:31
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.49 kb
//30 puncte pe Infoarena - memorie

#include <fstream>
#include<algorithm>

using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");

struct nod
  {int inf;
   nod *urm;
  }*l[100001];

int n, m, nr, k;
int t[100001], niv[100001], low[100001], st[100001][2], v[200001];
bool VIZ[100001];

void adaug(nod *&p,int x)
{
   nod *c=new nod;
   c->inf=x;
   c->urm=p;
   p=c;
}


void push (int x, int y)
 {
     st[++k][0]=x;
     st[k][1]=y;
 }

void pop (int &x, int &y)
{
    x=st[k][0];
    y=st[k][1];
    k--;
}

void DF(int i)
{nod *c;

VIZ[i]=1;
low[i]=niv[i];

for(c=l[i];c;c=c->urm)

  if (!VIZ[c->inf])

    { niv[c->inf] = niv[i]+1;
      t[c->inf]=i;
      DF(c->inf);
      low[i]=min(low[i],low[c->inf]);

      if (low[c->inf]>=niv[i]) // i e punct de articulatie, deci din c->inf nu se poate ajunge mai sus de tatal sau
         nr++;  // numar componenta biconexa
    }

   else if (c->inf!=t[i])
          low[i]=min(low[i],niv[c->inf]);

}

void DF1(int i)
{nod *c;
int x,y,k1,j;

VIZ[i]=1;
low[i]=niv[i];

for(c=l[i];c;c=c->urm)
{
  if (c->inf!=t[i] && niv[i]>niv[c->inf])
    push (i, c->inf); // adaug muchia de intoarcere in stiva

  if (!VIZ[c->inf])

    { niv[c->inf] = niv[i]+1;
      t[c->inf]=i;
      DF1(c->inf);
      low[i]=min(low[i],low[c->inf]);

      if (low[c->inf]>=niv[i])
     // i e punct de articulatie, deci din c->inf nu se poate ajunge mai sus de tatal sau
          {
             k1=0;
             do // afisez componenta biconexa
               {
                 pop (x,y); // operatia de extragere din stiva se opreste la muchia [x,t[x]]
                 v[++k1]=x; v[++k1]=y; // g<<x<<" "<<y; muchia din componenta

               } while ((x!=i || y!=c->inf) &&  (x!=c->inf || y!=i));

              sort(v+1,v+k1+1);
              g<<v[1]<<" ";
              for (j=2;j<=k1;j++)
                  if (v[j]!=v[j-1]) g<<v[j]<<" ";
              g<<'\n';
           }

    }

   else if (c->inf!=t[i])
          low[i]=min(low[i],niv[c->inf]);

}
}

int main()
{   int x,y,i;

    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        adaug(l[y],x);
        adaug(l[x],y);
    }

    niv[1]=1; // daca graful e conex
    DF(1);
    g<<nr<<'\n';

    for (i=1;i<=n;i++)
    {
        VIZ[i]=0;
        niv[i]=0;
        low[i]=0;
        t[i]=0;
    }

    niv[1]=1; // daca graful e conex
    DF1(1);

    g.close();
    return 0;
}