Cod sursa(job #1095759)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 31 ianuarie 2014 20:23:34
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
// Tarjan - O(N+M)- CutVertex
//low[i] = cea mai mica valoare din subarborele lui i
//found[i] = al catelea nod vizitat este nodul i (ordine cronologica)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define Nmax 100099
#define NIL -1
#define x first
#define y second
#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];
vector < vector < int > > BCC; //componente biconexe
stack  < edge > st;

void Tarjan(),ExtractBCC(edge M),PrintBCC(),PrintCE(),PrintCV(),ReadInput();

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
               ExtractBCC(edge(node,*it));
          if(T[node] && low[*it]>=found[node])
               ExtractBCC(edge(node,*it));

      }
      else
  	   if(*it!=T[node])low[node]=min(low[node],found[*it]);
}

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

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

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 > 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')
          for(vector<int> ::iterator it=BCC[i].begin();it!=BCC[i].end();++it)
               g<<*it<<' ';
}

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);
}