Cod sursa(job #600387)

Utilizator nervousNervous nervous Data 1 iulie 2011 15:56:48
Problema Componente biconexe Scor 34
Compilator cpp Status done
Runda Arhiva educationala Marime 2.34 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>

#define X1 100001

using namespace std;

ifstream in;
ofstream out;

vector <int> v[X1],biconex[X1];
stack <pair<int,int> > st;

int use[X1],T[X1],level[X1],low[X1],er[X1];
int cnt=0;

inline void df(int nod)
{
    int x,y;

    use[nod]=1;
    for(vector <int>::iterator it=v[nod].begin();it!=v[nod].end();++it)
    {
        if(T[nod]!=*it) st.push(make_pair(*it,nod));
        if(!use[*it])
        {
            T[*it]=nod;
            level[*it]=level[nod]+1;
            low[*it]=level[*it];
            df(*it);
            if(low[nod]>low[*it]) low[nod]=low[*it];
            if(low[*it]>=level[nod])
            {
                memset(er,0,sizeof(er));
                ++cnt;
                x=st.top().first;
                y=st.top().second;
                if((x!=*it||y!=nod)&&(x!=nod||y!=*it))
                {
                    do
                    {
                        x=st.top().first;
                        y=st.top().second;
                        if(!er[y]) er[y]=1,biconex[cnt].push_back(y);
                        else
                        if(!er[x]) er[x]=1,biconex[cnt].push_back(x);
                        st.pop();
                    }
                    while((x!=*it||y!=nod)&&(x!=nod||y!=*it)&&st.size());
                }
                else
                {
                    biconex[cnt].push_back(x);
                    biconex[cnt].push_back(y);
                }
            }
        }
        else
        if(T[nod]!=*it)
            if(low[nod]>level[*it])
                low[nod]=level[*it];
    }
}

int main()
{
    int M,N,x,y;

    in.open("biconex.in");
    in>>N>>M;
    for(;M;--M)
    {
        in>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    in.close();

    memset(use,0,sizeof(use));
    memset(level,0,sizeof(level));
    memset(low,0,sizeof(low));
    memset(T,0,sizeof(T));

    for(int i=1;i<=N;++i)
        if(!use[i])
            df(i);

    out.open("biconex.out");
    out<<cnt<<'\n';
    for(int i=1;i<=cnt;++i)
    {
        for(vector <int>::iterator it=biconex[i].begin();it!=biconex[i].end();++it)
            out<<*it<<' ';
        out<<'\n';
    }
    out.close();

    return 0;
}