Cod sursa(job #1166181)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 3 aprilie 2014 12:36:20
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.56 kb
// Tarjan - O(N+M)
// CutVertex+CriticalEdges+BCC

#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#define Nmax 100099
#define pb push_back
#define x first
#define y second
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
typedef pair<int,int> edge;

int N,M,x,y,order,found[Nmax],low[Nmax],T[Nmax];
vector< int > G[Nmax];
vector < int> CV; //CutVertex
vector < edge > CE; // CriticalEdges
stack < edge > st;
vector < vector < int > > BCC;

void ReadInput(),PrintCV(),PrintCE(),PrintBCC();
void GetBCC(edge M);

template < class T>
inline void EliminateDuplicates(vector < T > &v)
{
     sort(v.begin(),v.end());
     v.erase(unique(v.begin(),v.end()),v.end());
}

void DFS(int node)
{
     found[node]=low[node]=++order;
     for(vector<int>::iterator it=G[node].begin();it!=G[node].end();++it)
          if(!T[*it])
          {
               T[*it]=node , st.push(edge(node,*it));
               DFS(*it);
               low[node]=min(low[node],low[*it]);
               if(low[*it]>found[node])
                    CE.pb(edge(node,*it));
               if(low[*it]>=found[node])
               {
                    CV.pb(node);
                    GetBCC(edge(node,*it));
               }
          }
          else
               if(*it!=T[node])low[node]=min(low[node],found[*it]);
}

void Tarjan()
{
     for(int i=1;i<=N;++i)
          if(!T[i])T[i]=i,DFS(i);
     EliminateDuplicates(CV);
     EliminateDuplicates(CE);
}

int main()
{
     ReadInput();
     Tarjan();
     //PrintCV();
     //PrintCE();
     PrintBCC();
     f.close();g.close();
     return 0;
}

void ReadInput()
{
     f>>N>>M;
     for(int i=1;i<=M;++i)
          f>>x>>y , G[x].pb(y) , G[y].pb(x);
}

void GetBCC(edge M)
{
     vector < int > newBCC;
     edge E;
     do{
          E=st.top(); st.pop();
          newBCC.pb(E.x), newBCC.pb(E.y);
       }while(E!=M);
     EliminateDuplicates(newBCC);
     BCC.pb(newBCC);
}
void PrintCV()
{
     g<<CV.size()<<'\n';
     for(vector<int>::iterator it=CV.begin();it!=CV.end();++it)
          g<<*it<<' ';
     g<<'\n';
}

void PrintCE()
{
     g<<CE.size()<<'\n';
     for(vector<edge>::iterator it=CE.begin();it!=CE.end();++it)
          g<<it->x<<' '<<it->y<<'\n';
}

void PrintBCC()
{
     g<<BCC.size()<<'\n';
     for(int i=0;i<BCC.size();++i)
     {
          g<<BCC[i].size()<<' ';
          for(vector<int>::iterator it=BCC[i].begin();it!=BCC[i].end();++it)
               g<<*it<<' ';
          g<<'\n';
     }
}