Cod sursa(job #1166355)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 3 aprilie 2014 15:03:29
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 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);

    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);

            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]);
}

int main()
{
    f>>N>>M;
    for(int i=1;i<=M;++i)
        f>>x>>y , G[x].pb(y) , G[y].pb(x);
    for(int i=1;i<=N;++i)
        if(!T[i]) T[i]=i , DFS(i);
    MakeUnique(CV);
    MakeUnique(CE);

    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';
    }
    return 0;

}