Cod sursa(job #1166383)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 3 aprilie 2014 15:34:50
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.38 kb
#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,x,y,low[Nmax],found[Nmax],order,T[Nmax];

vector < int > G[Nmax],CV;
vector < PP > CE;
vector < vector < int > > BCC;
stack < PP > st;

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

inline 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);
    BCC.pb(v);
}

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

            DFS(*it);

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

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

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

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

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

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

inline void PrintBiconnectedComponents()
{
    g<<BCC.size()<<'\n';
    for(int i=0;i<BCC.size();++i)
    {
        //g<<BCC[i].size()<<' ';
        for(vector<int>::iterator it=BCC[i].begin();it!=BCC[i].end();++it)
            g<<*it<<' ';
        g<<'\n';
    }
}
int main()
{
    f>>N>>M;
    for(int i=1;i<=M;++i)
        f>>x>>y , G[x].pb(y) , G[y].pb(x);
    Tarjan();
    //PrintCutVertex();
    //PrintCriticalEdge();
    PrintBiconnectedComponents();
    f.close();g.close();
    return 0;
}