Cod sursa(job #484340)

Utilizator APOCALYPTODragos APOCALYPTO Data 13 septembrie 2010 18:10:32
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
#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);

}
void dfs(int v,int tata,int lev)
{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(w!=tata&&(niv[w]<niv[v]))
        {
            S.push((much){v,w});
        }
            if(niv[w]==0)
            {    //S.push((much){v,w});
                dfs(w,v,lev+1);
                if(niv[v]<=low[w])
                {   toleranta++;
                    //cout<<"\n";
                    extrage(v,w);
                }
                low[v]=min(low[v],low[w]);
            }

            else

            low[v]=min(low[v],niv[w]);


    }





}
int main()
{int i,mos=-1;;
vector<int>::iterator it;
    cit();
    dfs(1,0,1);
    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();
}