Cod sursa(job #1420909)

Utilizator code_and_rosesUPB Dinu Neatu Rotaru code_and_roses Data 19 aprilie 2015 09:50:43
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.94 kb
// Tarjan - O(N+M)
// cutVertex + criticalEdge + BiconnetedComponets

#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#define Nmax 100009
#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> PP;

int N, M;
vector<int> G[Nmax];

int low[Nmax], found[Nmax], order, T[Nmax];

vector<int> cutVertex;
vector<PP> criticalEdge;
vector< vector <int> > biconexComponents;
stack<PP> st;


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


void GetBCC(PP E) {
    vector<int> v;
    PP aux;
    do{
      aux = st.top();
      st.pop();
      v.pb(aux.x);
      v.pb(aux.y);
    }while(aux != E);

    makeUnique(v);

    biconexComponents.pb(v);
}

inline void DFS(const 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]){
        ++children , T[*it]=node , st.push(PP(node,*it));

        DFS(*it);

        low[node]=min(low[node],low[*it]);

        if(T[node] == node && children > 1) cutVertex.pb(node);
        

        if(T[node] != node && low[*it] >= found[node]) cutVertex.pb(node);
      

        if(low[*it] >= found[node]) GetBCC(PP(node,*it));

        if(low[*it] > found[node]) criticalEdge.pb(PP(node,*it));
    }
    else 
      if(*it != T[node])
         low[node] = min(low[node],found[*it]);
}

void Tarjan()
{
    for(int i = 1; i <= N; ++i)
      if(!T[i]) { /* nu are tata <=> nu a mai fost vizitat */
        T[i]=i;
        DFS(i);
      }

    makeUnique(cutVertex);
    
    makeUnique(criticalEdge);
}

void ReadInput(), PrintCutVertex(), PrintCriticalEdge(), PrintBiconnectedComponents();

int main()
{
    ReadInput();
    Tarjan(); 
    //PrintCutVertex();
    //PrintCriticalEdge();
    PrintBiconnectedComponents();
    f.close();g.close();
    return 0;
}



void PrintCutVertex() {
  g << cutVertex.size() << '\n';
  for(vector<int>::iterator it = cutVertex.begin(); it != cutVertex.end(); ++it) {
    g << *it << ' ';
  }
  g<<'\n';
}

void PrintCriticalEdge() {
  g << criticalEdge.size() << '\n';
  for(vector<PP>::iterator it = criticalEdge.begin(); it != criticalEdge.end(); ++it) {
    g<< it->x << ' ' << it->y << '\n';
  }
}

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

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