Cod sursa(job #601818)

Utilizator yonatanCont de teste yonatan Data 7 iulie 2011 22:29:49
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<stack>
#include<set>
#define nmax 100010
#define pb push_back
struct edge{
int x,y;};
stack<edge> S;
int N,M;
vector<int> G[nmax];
int h=0;
int low[nmax],def[nmax];
ofstream fout("biconex.out");

vector<vector<int> > comp;

void extrage(int x,int y)
{
    edge dummy;
    vector<int> con;
    do
    {
        dummy=S.top();
        S.pop();
        con.pb(dummy.x);
        con.pb(dummy.y);

    }
    while(x!=dummy.x || y!=dummy.y);
    comp.pb(con);
}

void dfs(int x,int t)
{
    h++;
    def[x]=h;
    low[x]=h;
    int y;
    vector<int>::iterator it;
    for(it=G[x].begin();it<G[x].end();it++)
    {
        y=*it;
        if(y!=t)
        {
        if(def[y]==0) //muchie de arbore
        {
            S.push((edge){x,y});
            dfs(y,x);
            low[x]=min(low[x],low[y]);
            if(low[y]>=def[x])
            {
                extrage(x,y);
            }
        }
        else if(def[x]>def[y]) //daca x->y e muchie inainte, nu muchie de inaintare
        {
            S.push((edge){x,y});
            low[x]=min(low[x],low[y]);

        }
        }
    }

}

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);
    }
    fin.close();

}

int main()
{
   cit();
   dfs(1,0);
   vector<vector<int> >::iterator it;
   vector<int>::iterator jt;
   fout<<comp.size()<<"\n";
   for(it=comp.begin();it<comp.end();it++)
   {
       sort(it->begin(),it->end());
       (*it).erase(unique(it->begin(),it->end()),it->end());
       for(jt=it->begin();jt<it->end();jt++)
       {
           fout<<*jt<<" ";
       }
       fout<<"\n";
   }
   fout.close();

   return 0;
}