Cod sursa(job #1167104)

Utilizator ThomasFMI Suditu Thomas Thomas Data 4 aprilie 2014 12:57:52
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 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,nr,nrsol;
vector<int> v[NMax],sol[NMax];
stack< pair<int, int> > st;
int dfn[NMax],low[NMax],viz[NMax],viz2[NMax],Art[NMax];

void afis(int x,int y)
{
    ++nrsol;
    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);
}

void DFS(int s,int ps,int number)
{
    dfn[s]=low[s]=number;
    for(int i=0;i<(int)v[s].size();i++) if(ps!=v[s][i])
    {
        if(dfn[v[s][i]]==-1)
        {
            st.push( make_pair(s,v[s][i]) );
            DFS(v[s][i],s,number+1);
            low[s]=min(low[s],low[v[s][i]]);
            if(low[v[s][i]]>=dfn[s])
            {
                Art[s]=1;
                afis(s,v[s][i]);
            }
        }
        else
        {
           low[s]=min(low[s],dfn[v[s].at(i)]);
        }
    }
}

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

    for(i=1;i<=n;i++) dfn[i]=-1;

    DFS(1,0,0);

    g<<nrsol<<"\n";
    for(i=1;i<=nrsol;i++)
    {
        sort(sol[i].begin(),sol[i].end());
        g<<sol[i][0]<<" ";
        for(a=1;a<(int)sol[i].size();a++) if(sol[i][a]!=sol[i][a-1]) g<<sol[i][a]<<" ";
        g<<"\n";
    }

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