Cod sursa(job #1095651)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 31 ianuarie 2014 17:07:52
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.75 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>
#define Nmax 100099
#define NIL -1
#define x first
#define y second
#define mp make_pair
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;
stack  < edge > st;

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)
{
    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);
            // 	Check if the subtree rooted with *it has a              				connection to one of the ancestors of node
          if(low[*it]<low[node])low[node]=low[*it];
            		// node is an articulation point in following cases
            		// (1) node is root of DFS tree and has two or more 					chilren.
          if (T[node]==NIL && children>1)
          {    cutPoint[node]=1;
               edge M;
               do
               {
                    M=st.top(); st.pop();
                    g<<M.x<<' '<<M.y<<' ';
               }while(M!=edge(node,*it));
               g<<'\n';
          }
            		// (2) If node is not root and low value of one of 						its child is more
            		// than discovery value of node.
          if(T[node]!=NIL && low[*it]>found[node])cutPoint[node]=1;
          if(T[node]!=NIL && low[*it]>=found[node])
          {
               cutPoint[node]=1;
               edge M;
               do
               {
                    M=st.top(); st.pop();
                    g<<M.x<<' '<<M.y<<' ';
               }while(M!=edge(node,*it));
               g<<'\n';
          }
      }
        // Update low value of node for parent function calls.
      else
  	   if(*it!=T[node] && found[*it]<low[node])low[node]=found[*it];
}




void Tarjan(),ReadInput();

int main()
{
    ReadInput();
    Tarjan();
    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);
    //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);
    }
}