Cod sursa(job #884219)

Utilizator zeeboBuzatu Vlad zeebo Data 20 februarie 2013 19:40:48
Problema Componente biconexe Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 2.05 kb
#include <fstream>
#include <vector>
#define pb push_back
#define INF 0x3f3f3f3f
using namespace std;

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

int n,m,i,x,y,T[100001],Niv[100001],L[100001],nr,stiva[100001],ns=1,pozs,pc,nrcomp;
bool sel[100001],use[100001],PC[100001],stv[100001];
vector <int> G[100001];


void DFSP (int nod)
{
    vector <int> :: iterator it;
    vector <int> :: iterator it1;

    sel[nod]=true;
    for (it=G[nod].begin(); it!=G[nod].end(); it++)
      if (!sel[*it])
      {
         T[*it]=nod;
         Niv[*it]=Niv[nod]+1;
         if (nod==1) nr++;
         DFSP(*it);
      }

    for (it1=G[nod].begin(); it1!=G[nod].end(); it1++)
     if (L[nod]>Niv[*it1])
        {
          L[nod]=Niv[*it1];
          int x=nod;
          while (L[x]<L[T[x]])
          {
             L[T[x]]=L[x];
             x=T[x];
          }
        }
}

void DFSS (int nod, int pozs)
{

   vector <int> :: iterator it;

    use[nod]=true;
    for (it=G[nod].begin(); it!=G[nod].end(); it++)
       if (!use[*it])
       {
           stiva[++ns]=*it;
           stv[*it]=true;
           DFSS(*it,pozs);
       }

    for (it=G[nod].begin(); it!=G[nod].end(); it++)
       if (PC[*it] && stv[*it])
       {
           bool ok=false;
           while (stiva[ns]!=*it)
            {
               if (pozs==0) g<<stiva[ns]<<' ';
               stv[stiva[ns]]=false;
               stiva[ns]=0;
               ns--;
               ok=true;
            }
            if (ok && pozs==0) g<<*it<<'\n'; else if (ok) nrcomp++;
       }
}
int main ()
{
   f>>n>>m;
   for (i=1;i<=m;i++)
   {
       f>>x>>y;
       G[x].pb(y);
       G[y].pb(x);
   }

   for (i=1;i<=n;i++) L[i]=INF;

Niv[1]=1, T[1]=0, L[1]=1;
DFSP(1);

if (nr>1) PC[1]=true;
for (i=2;i<=n;i++)
   if (L[i]>=Niv[T[i]] && T[i]!=1) PC[T[i]]=true, pc=T[i];

stiva[1]=pc; stv[pc]=true;

DFSS(pc,1);
g<<nrcomp<<'\n';

for (i=1;i<=n;i++) stiva[i]=0,stv[i]=use[i]=false;
stv[pc]=true, stiva[1]=pc;

DFSS(pc,0);

return 0;
}