Cod sursa(job #2348417)

Utilizator Anca.ioanaMuscalagiu Anca Ioana Anca.ioana Data 19 februarie 2019 18:18:52
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
#include <stdio.h>
#include <stack>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int nma[100001], nivel[100001],n, tata,Viz[100001],radacina,m,nrc,componente;
vector <int> L[100001],C[100001];
stack <int> S;
void Citire()
{int i, x, y;
 f>>n>>m;
    for(i=1;i<=m;i++)
    { f>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }
}
/*void dfs(int k)
{ int j;
    Viz[k]=1;
    for(j=0;j<L[k].size();j++)
      if(Viz[L[k][j]]==0)
       { tata[L[k][j]]=k;
        dfs(L[k][j]);}
}
*/
void pct(int k, int x)
{
    if(nivel[k]<=nma[x]&&k!=radacina)
        cout<<k<<" ";

}
void punte(int k,int x)
{
if(nivel[k]< nma[x])
 cout<<k<<" "<<x<<endl;

}
void comp(int k,int x)
{int nr;
if(nivel[k]<=nma[x])
  {while(S.top()!=x)
  { nr=S.top();
      C[nrc].push_back(nr);
      S.pop();
  }
  C[nrc].push_back(x);
   S.pop();
  C[nrc].push_back(k);
  componente++;}
}
void dfs2(int k,int tata)
{ Viz[k]=1;
  S.push(k);
    nivel[k]=nivel[tata]+1;
    nma[k]=nivel[k];
int j,x;
for(j=0;j<L[k].size();j++)
  { x=L[k][j];
     if(x!=tata)
     { if(Viz[x]==1)
          { if(nma[k]>nivel[x])
              nma[k]=nivel[x];
          }
       else  {
            dfs2(x,k);
               if(nma[k]>nma[x])
                 nma[k]=nma[x];

              // pct(k,x);
             // punte(k,x);

 nrc++;
            comp(k,x);

             }
     }
  }
}
void afisare()
{ int i ,j,nr=0 ;

    g<<componente<<endl;
    for(i=1;i<=nrc;i++)
        {for(j=0;j<C[i].size();j++)
         g<<C[i][j]<<" ";
         if(C[i].size()!=0)
     g<<endl;}
}
int main()
{
Citire();
radacina=1;
//nivel[radacina]=1;
//nma[radacina]=1;
//dfs(radacina);
memset(Viz, 0, sizeof(Viz));
dfs2(radacina,1);
afisare();

f.close();
g.close();
    return 0;
}