Cod sursa(job #484400)

Utilizator APOCALYPTODragos APOCALYPTO Data 13 septembrie 2010 23:54:52
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.31 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&&(niv[w]<niv[v]))
        {
            S.push((much){v,w});
        }
            if(niv[w]==0)
            {    //S.push((much){v,w});
                dfs(w,v);
                low[v]=min(low[v],low[w]);
                if(niv[v]<=low[w])
                {   toleranta++;
                    //cout<<"\n";
                    extrage(v,w);
                }

            }

            else
            if(tata!=w)
            low[v]=min(low[v],niv[w]);


    }





}
char a[100000],b[100000];
/*void main1()
{int i=1,ok=1;
    ifstream fin("biconex1.out");
    ifstream fin1("grader_test5.ok");
    do
    { fin.getline(a,10000);
      fin1.getline(b,10000);
        if(strcmp(a,b)==0)
         i++;
        else
        ok=0;
    }
    while(ok);
    cout<<i<<" ";

}*/
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";
    }
    //main1();
    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();
}