Cod sursa(job #1095706)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 31 ianuarie 2014 18:39:27
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.08 kb
// Tarjan - O(N+M)- CutVertex
//low[i] = cea mai mica valoare din subarborele lui i
//found[i] = al catelea nod vizitat e i (ordine cronologica)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define Nmax 100099
#define NIL -1
#define x first
#define y second
#define mp make_pair
#define pb push_back
using namespace std;
ifstream f("biconex.in");ofstream g("biconex.out");
typedef pair<int,int> edge;

int N,T[Nmax],low[Nmax],found[Nmax],order;
vector < int > G[Nmax],sol[Nmax],CutVertex;
stack  < edge > st;
vector < vector < int > > BCC;
vector < edge > CriticalEdge;


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


void ExtractBCC(edge M)
{
     vector < int > newcomp;
     edge current;
     do
     {
          current=st.top(); st.pop();
          newcomp.pb(current.x);
          newcomp.pb(current.y);
     }while(current!=M);
     EliminateDuplicates(newcomp);
     BCC.pb(newcomp);
}

void DFS(int node)
{
    int children=0;
    found[node] = low[node] = ++order;
    for (vector<int>::iterator it=G[node].begin();it!=G[node].end();++it)
      if (!T[*it]) // nu are tata = nu a fost vizitat sau e radacina DFS
      {
          ++children , T[*it]=node, st.push(edge(node,*it));
          DFS(*it);
          low[node]=min(low[node],low[*it]);
          if (!T[node] && children>1) //e radacina arborelui DFS
          {
               CutVertex.pb(node);
               ExtractBCC(edge(node,*it));
               CriticalEdge.pb(edge(node,*it));

          }
          if(T[node] && low[*it]>=found[node])
          {
               CutVertex.pb(node);
               ExtractBCC(edge(node,*it));
               if(low[*it]>found[node])
                    CriticalEdge.pb(edge(node,*it));
          }
      }
      else
  	   if(*it!=T[node])low[node]=min(low[node],found[*it]);
}




void Tarjan(),PrintBiconnectedComponents(),PrintCriticalEdges(),PrintCriticalNodes(),ReadInput();

int main()
{
    ReadInput();
    Tarjan();
    //PrintCriticalNodes();
    //PrintCriticalEdges();
    PrintBiconnectedComponents();
    return 0;
}

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

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

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

void PrintCriticalNodes()
{
     EliminateDuplicates(CutVertex);
     g<<CutVertex.size()<<'\n';
     for(vector<int>::iterator it=CutVertex.begin();it!=CutVertex.end();++it)
          g<<*it<<' ';
     g<<'\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);
}