Cod sursa(job #2175393)

Utilizator BotzkiBotzki Botzki Data 16 martie 2018 16:58:48
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX=100000;
struct muchie
{
   int x, y;
};
stack <muchie> st;
int T[NMAX+5], niv[NMAX+5], low[NMAX], nivel, sol, n;
vector <int>G[NMAX+5], B[NMAX+5];
void componenta(int x, int y)
{
    int i, j;
    sol++;
    do
    {
        i=st.top().x;
        j=st.top().y;
        st.pop();
        B[sol].push_back(j);
    }while(i!=x and j!=y);
    B[sol].push_back(x);

}
void DFS(int nod)
{
    int fiu, j;
    muchie a;
    nivel++;
    int it;
    niv[nod]=low[nod]=nivel;
    for(j=0;j<G[nod].size();j++)
    {
        it=G[nod][j];
        fiu=it;
        if(it!=T[nod])
        {
            if(!niv[fiu])
            {
                a.x=nod;
                a.y=fiu;
                st.push(a);
                T[fiu]=nod;
                DFS(fiu);
                if(low[fiu]>=niv[nod])
                    componenta(nod, fiu);
                low[nod]=min(low[nod], low[fiu]);
            }
            else
                low[nod]=min(low[nod], niv[fiu]);


        }
    }
}

int main()
{
    int i, m, xi, yi;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>xi>>yi;
        G[xi].push_back(yi);
        G[yi].push_back(xi);
    }
    for(i=1;i<=n;i++)
    {
        if(!niv[i])
            DFS(i);
    }
    fout<<sol<<"\n";
    int j;
    for(i=1;i<=sol;i++)
    {
        for(j=0;j<B[i].size();j++)
            fout<<B[i][j]<<" ";
        fout<<"\n";
    }


    return 0;
}