Cod sursa(job #1120345)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 24 februarie 2014 23:19:27
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.74 kb
// Tarjan - O(N+M)
// low[i]= cea mai mica valoare din subarborele lui i
// found[i]= numarul de ordine a lui i din parcurgerea DFS
#include <fstream>
#include <vector>
#include <algorithm>
#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;
typedef vector<int>::iterator xxit;
typedef vector<edge>::iterator edgeit;
int N,T[Nmax],low[Nmax],found[Nmax],order;
vector < int > G[Nmax];
vector < int > CV; //CutVertex
vector < vector < int > > BCC; //Biconnected Commponents
vector < edge > CE; //Critical Edges
stack  < edge > st;

void Tarjan(),DFS(int node),GetBCC(edge M),ReadInput(),PrintCV(),PrintBCC(),PrintCE();

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

int main()
{
     ReadInput();
     Tarjan();
     //PrintCV();
     //PrintCE();
     PrintBCC();
     return 0 ;
}

template<class T>
inline void EliminateDuplicates(vector<T> &v)
{
     sort(v.begin(),v.end());
     v.erase( unique(v.begin(),v.end()) , v.end());
}
void Tarjan()
{
     for(int i=1;i<=N;++i)
          if(!T[i])T[i]=i,DFS(i);
     EliminateDuplicates(CV);
     EliminateDuplicates(CE);
}

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 PrintBCC()
{
     g<<BCC.size()<<'\n';
     for(int i=0;i<BCC.size();++i,g<<'\n')
          {
               //g<<BCC[i].size()<<' ';
               for(xxit it=BCC[i].begin();it!=BCC[i].end();++it)
               g<<*it<<' ';
}
          }

void PrintCV()
{
     g<<CV.size()<<'\n';
     for(xxit it=CV.begin();it!=CV.end();++it)
          g<<*it<<' ';
     g<<'\n';
}
void PrintCE()
{
     g<<CE.size()<<'\n';
     for(edgeit it=CE.begin();it!=CE.end();++it)
          g<<it->x<<' '<<it->y<<'\n';
}

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