Cod sursa(job #1412704)

Utilizator ThomasFMI Suditu Thomas Thomas Data 1 aprilie 2015 13:58:11
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

#define NMax 100005

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

int n,m,nrsol;
int dfn[NMax],low[NMax];
bool Art[NMax];
vector<int> v[NMax],sol[NMax];
stack< pair<int,int> > st;

void afis(int x,int y)
{
    int tx,ty;
    do
    {
        tx = st.top().first;
        ty = st.top().second;
        st.pop();
        sol[nrsol].push_back(tx);
        sol[nrsol].push_back(ty);
    } while(tx != x || ty != y);

    sort(sol[nrsol].begin(),sol[nrsol].end());
}

void DFS(int nod,int parinte,int nivel)
{
    dfn[nod] = low[nod] = nivel;
    for(int i=0;i<v[nod].size();++i) if(v[nod][i] != parinte)
    {
        if(!dfn[v[nod][i]]) //muchie a arborelui
        {
            st.push(make_pair(nod,v[nod][i]));
            DFS(v[nod][i],nod,nivel+1);
            low[nod] = min(low[nod],low[v[nod][i]]);
            if(low[v[nod][i]] >= dfn[nod])
            {
                Art[i] = true;
                ++nrsol;
                afis(nod,v[nod][i]);
            }
        }
        else // muchie de intoarcere
        {
            low[nod] = min(low[nod],dfn[v[nod][i]]);
        }
    }
}

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

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

    DFS(1,0,1);

    g<<nrsol<<"\n";
    for(i=1;i<=nrsol;++i)
    {
        g<<sol[i][0]<<" ";
        for(j=1;j<sol[i].size();++j) if(sol[i][j] != sol[i][j-1]) g<<sol[i][j]<<" ";
        g<<"\n";
    }

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