Cod sursa(job #1095672)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 31 ianuarie 2014 17:29:59
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.68 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 <bitset>
#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");

int N,M,T[Nmax],low[Nmax],found[Nmax],order;
vector < int > G[Nmax],sol[Nmax];
bitset < Nmax > viz,cutPoint;
typedef pair<int,int> edge;
typedef vector < int > Vect;
stack  < edge > st;
vector < Vect > ConnectedComponents;
template<class T>
inline void EliminateDuplicates(vector<T> &v)
{
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}


void ExtrageComponenta(edge M)
{
     Vect newcomp;
     edge current;
     do
     {
          if(st.empty())break;
          current=st.top(); st.pop();
          newcomp.pb(current.x);
          newcomp.pb(current.y);
     }while(current!=M);
     EliminateDuplicates(newcomp);
     ConnectedComponents.pb(newcomp);
}
void DFS(int node)
{
    int children=0;
    viz[node]=1; found[node] = low[node] = ++order;
    vector<int>::iterator it;
    for (it=G[node].begin();it!=G[node].end();++it)
      if (!viz[*it])
      {
          st.push(edge(node,*it));
          ++children;
          T[*it]=node;
          DFS(*it);
          if(low[*it]<low[node])low[node]=low[*it];
          if (T[node]==NIL && children>1)
          {    cutPoint[node]=1;
               ExtrageComponenta(edge(node,*it));
          }
          if(T[node]!=NIL && low[*it]>found[node])cutPoint[node]=1;
          if(T[node]!=NIL && low[*it]>=found[node])
          {
               cutPoint[node]=1;
               ExtrageComponenta(edge(node,*it));
          }
      }
      else
  	   if(*it!=T[node] && found[*it]<low[node])low[node]=found[*it];
}




void Tarjan(),ReadInput();

int main()
{
    ReadInput();
    Tarjan();
     g<<ConnectedComponents.size()<<'\n';
     for(int i=0;i<ConnectedComponents.size();++i,g<<'\n')
          for(vector<int> ::iterator it=ConnectedComponents[i].begin();it!=ConnectedComponents[i].end();++it)
               g<<*it<<' ';
    return 0;
}

void Tarjan()
{
    for (int i=1; i<=N;++i)T[i]=NIL;
    for (int i=1; i<=N;++i)
        if (!viz[i])DFS(i);
     ExtrageComponenta(edge(0,0));
    //for (int i =1;i<=N;++i)
        //if (cutPoint[i])g<<i<<' ';

}

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