Cod sursa(job #1746002)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 22 august 2016 17:10:12
Problema Componente biconexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m,v[100001],low[100001],nrb,i,vfS,nr;
vector<vector<int>>sol;
int Min(int a,int b){
   if (a<b) return a;
   return b;
}
struct nod{
   int inf;
   nod *urm;
}*L[100001];
struct muchie{
   int f,t;
}S[100001];
void adaugsf(nod *&vf,int val){
   nod *q;
   q=new nod;
   q->inf=val;
   q->urm=vf;
   vf=q;
}
void cit(){
   int a,b;
   fin>>n>>m;
   for (i=1;i<=n;i++)
     L[i]=0;
   for (i=1;i<=m;i++){
      fin>>a>>b;
      adaugsf(L[a],b);
      adaugsf(L[b],a);
   }
   fin.close();
}
void actualizare(int nod,int t){
    vector<int>aux;
    muchie i;
    nrb++;
     do{
        i=S[vfS];
        aux.push_back(i.t);aux.push_back(i.f);
        vfS--;
     }while(i.t!=t || i.f!=nod);
     sol.push_back(aux);
}
void DFS(int nd,int t){
     nod *q;
     nr++;
     v[nd]=nr;low[nd]=nr;
     q=L[nd];
     while(q!=0){
        if (v[q->inf]<v[nd] && q->inf!=t){
            vfS++;
            S[vfS].f=q->inf;S[vfS].t=nd;
        }
        if (v[q->inf]==0){
            DFS(q->inf,nd);
            low[nd]=Min(low[nd],low[q->inf]);
            if (low[nd]>=v[nd]) actualizare(q->inf,nd);
        }
          else
            if (q->inf!=t) low[nd]=Min(low[nd],v[q->inf]);
        q=q->urm;
     }
}
int main(){
   cit();
   S[0].f=1;S[0].t=-1;vfS=0;
   DFS(1,-1);
   fout<<sol.size()<<'\n';
   size_t l,j;
   for (l=0;l<sol.size();l++){
       sort(sol[l].begin(),sol[l].end());
       sol[l].erase(unique(sol[l].begin(),sol[l].end()),sol[l].end());
       for (j=0;j<sol[l].size();j++)
         fout<<sol[l][j]<<" ";
       fout<<'\n';
   }
   fout.close();
   return 0;
}