Cod sursa(job #1746061)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 22 august 2016 17:39:44
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 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 (q->inf!=t)
        if (v[q->inf]==-1){
            vfS++;
            S[vfS].f=q->inf;S[vfS].t=nd;
            DFS(q->inf,nd);
            low[nd]=Min(low[nd],low[q->inf]);
            if (low[q->inf]>=v[nd]) actualizare(q->inf,nd);
        }
          else
            low[nd]=Min(low[nd],v[q->inf]);
        q=q->urm;
     }
}
int main(){
   cit();
   S[0].f=1;S[0].t=-1;vfS=0;
   for (i=1;i<=n;i++){
      v[i]=low[i]=-1;
   }
   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;
}