Cod sursa(job #1121993)

Utilizator ThomasFMI Suditu Thomas Thomas Data 25 februarie 2014 15:14:44
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

#define NMax 100001
#define inf 210000000

ifstream f("biconex.in");
ofstream g("biconex.out");

int n,m,nr,nrsol;
vector<int> v[NMax],sol[NMax];
stack<int> st;
int dfn[NMax],low[NMax],viz[NMax],viz2[NMax],Art[NMax];

void afis(int s)
{
    ++nrsol;
    while(s!=st.top())
    {
        sol[nrsol].push_back(st.top());
        st.pop();
    }
    sol[nrsol].push_back(st.top());
}

void DF(int s)
{
    int i,e;
    viz2[s]=1;
    e=v[s].size();
    for(i=0;i<e;i++)
        if(viz2[v[s].at(i)]==0) DF(v[s].at(i));

    dfn[s]=n-(++nr)+1;
}

void DFS(int s,int ps)
{
    int i,e;
    low[s]=inf;
    viz[s]=1;

    st.push(s);

    e=v[s].size();
    for(i=0;i<e;i++) if(ps!=v[s].at(i))
    {
        if(viz[v[s].at(i)]==0)
        {
            DFS(v[s].at(i),s);
            if(low[s]>low[v[s].at(i)]) low[s]=low[v[s].at(i)];
            if(dfn[s]<=low[v[s].at(i)])
            {
                Art[s]=1;
                afis(s);
            }
        }
        else
        {
            if(low[s]>dfn[v[s].at(i)]) low[s]=dfn[v[s].at(i)];
        }
    }

    if(low[s]>dfn[s]) low[s]=dfn[s];
}

int main()
{
    int i,a,b;

    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    if(v[1].size()>1) Art[1]=1;

    DF(1);
    DFS(1,-1);

    g<<nrsol<<"\n";
    for(i=1;i<=nrsol;i++)
    {
        b=sol[i].size();
        for(a=b-1;a>=0;a--) g<<sol[i].at(a)<<" ";
        g<<"\n";
    }

    f.close();
    g.close();
    return 0;
}