Cod sursa(job #1120768)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 25 februarie 2014 10:00:01
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#define Nmax 100099
#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> edge;
int N,M,order,found[Nmax],low[Nmax],x,y,T[Nmax];
vector < int > G[Nmax],CV;
vector < vector < int >  >  BCC;
vector < edge > CE;
stack < edge > st;
void ReadInput()
{
    f>>N>>M;
    for(int i=1;i<=M;++i)
          f>>x>>y , G[x].pb(y), G[y].pb(x);
}


template <class T>
inline void EliminateDuplicates(vector < T > &v)
{
     sort(v.begin(),v.end());
     v.erase(unique(v.begin(),v.end()),v.end());
}
void GetBCC(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 DFS(int node)
{
     found[node]=low[node]=++order;
     for(vector<int>::iterator it=G[node].begin();it!=G[node].end();++it)
          if(!T[*it])
          {
               T[*it]=node , st.push(edge(node,*it));
               DFS(*it);
               low[node]=min(low[node],low[*it]);
               if(low[*it]>=found[node])
               {
                    CV.pb(node);
                    GetBCC(edge(node,*it));
               }
               if(low[*it]>found[node])
                    CE.pb(edge(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]) T[i]=i,DFS(i);
}

int main()
{
     ReadInput();
     Tarjan();
     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<<' ';
     g<<'\n';
     f.close();g.close();
     return 0;
}