Cod sursa(job #601469)

Utilizator APOCALYPTODragos APOCALYPTO Data 6 iulie 2011 19:29:46
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.53 kb
using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
#include<cstring>
//#include"verificator.cpp"
#define pb push_back
struct much{
int n1,n2;};
ofstream fout("biconex.out");
int t[100005],niv[100005],low[100005],N,M,toleranta;
vector<int> G[100005];
vector<vector<int> > sol;
stack<much> S;
void cit();
void extrage(int x,int y)
{   vector<int> con;
    much dummy;
    do
    {dummy=S.top();
    S.pop();
    //cout<<dummy.n1<<" "<<dummy.n2<<"     ";
    con.pb(dummy.n1);
    con.pb(dummy.n2);


    }
    while(dummy.n1!=x||dummy.n2!=y);
    sol.pb(con);
}

int lev=0;

void dfs(int v,int tata)
{vector<int>::iterator it;
int w;
    niv[v]=++lev;
    low[v]=lev;
    t[v]=tata;
    for(it=G[v].begin();it!=G[v].end();it++)
    {   w=*it;

        if(tata!=w)             //daca w nu e tatal lui u
        {
            if(niv[w]==0)        //daca w nu a fost vizitat (si este evident v->w e evident muchie de inaintare)
            {
                S.push((much){v,w});

                dfs(w,v);        //exploreaza subarborele
                low[v]=min(low[v],low[w]); //vezi daca dintre fii lui v ai gasit unul din care se poate ajunge mai sus decat v si updateaza
                if(niv[v]<=low[w])   //daca cel mai sus loc care in care se poate ajunge din w(si implicit din subarborele sau) este mai jos sau este v

                {
                    extrage(v,w);    //extrage componeneta biconexa
                }

            }

            else
            if(niv[w]<niv[v])
            { // ca sa nu bage si muchiile invers, daca muchia de intoarcere e 2->1 sa nu bage si 1->4
               S.push((much){v,w});
             //if(niv[w]>=niv[v]) cout<<v<<" "<<w<<" "<<niv[v]<<" "<<niv[w]<<"\n";
            low[v]=min(low[v],niv[w]);} //vezi daca nivelul lui w este mai sus de nivelul cel mai de sus la care se poate
            //ajunge din v pana la momentul respectiv si fa update.


         }
    }

}

int main()
{int i,mos=-1;;
vector<int>::iterator it;
    cit();
    dfs(1,0);
    fout<<sol.size()<<"\n";
    for(i=0;i<sol.size();i++)
    {sort(sol[i].begin(),sol[i].end());

    mos=-1;
    for(it=sol[i].begin();it!=sol[i].end();it++)
    if(*it!=mos)
      {

       mos=*it;
      fout<<*it<<" ";
      }
    fout<<"\n";
    }
    fout.close();
    return 0;
}

void cit()
{
    int i,x,y;
    ifstream fin("biconex.in");
    fin>>N>>M;
    for(i=1;i<=M;i++)
    {

      fin>>x>>y;
      G[x].pb(y);
      G[y].pb(x);
      //cout<<G[x].back()<<" "<<G[y].back()<<"\n";
    }
    fin.close();
}