Cod sursa(job #1623349)

Utilizator AvramAlexandraAvram Ioana-Alexandra AvramAlexandra Data 1 martie 2016 18:55:23
Problema Componente biconexe Scor 94
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>


using namespace std;

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

vector <int> L[100001],B[100001],low(100001),niv(100001);
bitset <100001> viz;
stack <int> Stack;
int n,t,cb,x,y,m;
void dfs(int nod,int tata)
{
    viz[nod]=1;
    t++;
    low[nod]=niv[nod]=t;
    Stack.push(nod);
     for(int i=0;i<L[nod].size();i++)
     {
         int vecin=L[nod][i];
          if(nod!=tata)
          {
              if(!viz[vecin])
              {
                  dfs(vecin,nod);
                  low[nod]=min(low[nod],low[vecin]);
                  if(low[vecin]>=niv[nod])
                  {
                       cb++;
                    do
                    {
                        int x=Stack.top();
                        Stack.pop();
                        B[cb].push_back(x);
                        if(x==vecin)break;

                    }while(x!=vecin);
                    B[cb].push_back(nod);
                  }
              }

          else low[nod]=min(low[nod],niv[vecin]);
          }
     }
    t--;
}
int main()
{
   f>>n>>m;
   for(int i=1;i<=m;i++)
   {
       f>>x>>y;
       L[x].push_back(y);
       L[y].push_back(x);
   }
   for(int i=1;i<=n;i++)
    if(!viz[i]) dfs(i,0);
g<<cb<<'\n';
   for(int i=1;i<=cb;i++)
   {
       for(int j=0;j<B[i].size();j++)
         g<<B[i][j]<<" ";
    g<<'\n';
   }


    return 0;
}