Cod sursa(job #2404639)

Utilizator Vlad_NituNitu Vlad-Petru Vlad_Nitu Data 13 aprilie 2019 10:55:50
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.28 kb
#include <bits/stdc++.h>
#define MAXIM 100005
using namespace std;
ifstream f ("biconex.in") ;
ofstream g ("biconex.out") ;
int N , M , nr = 0 , nr2 = 0;
int low[MAXIM] ,  niv[MAXIM] , t[MAXIM] , sol[MAXIM];
vector <int> v[MAXIM] ;
vector <pair <int ,int> > st;
void dfs (int k)
{
    int i , x ;
    low[k] = niv[k] ;
    int sz = v[k].size() ;
    for (int i  = 1 ; i < sz ; ++i)
    {
        x = v[k][i]; // vecin ;
        if (!niv[x]) // e nevizitat
        {
            niv[x] = niv[k] + 1 ;
            t[x] = k ; // k e tatal lui 'x';
            dfs(x) ;
            low[k] = min(low[k] , low[x]) ;
            if (low[x] >= niv[k]) nr ++; // k este pct de articulatie
        }
        else if (x != t[k]) low[k] = min(low[k],niv[x]) ;
    }
}
void reinitializare()
{
    for (int i = 1 ; i <= N  ; ++i)
        niv[i] = t[i] = low[i] = 0;
    return;
}
void dfs2(int k)
{
    int x , a1,a2;
    int var;
    low[k] = niv[k] ;
    int sz = v[k].size() ;
    for (int i = 0  ; i < sz ; ++i)
    {
        x = v[k][i];
        if (!niv[x])
        {
            niv[x] = niv[k] + 1;
            t[x] = k;
            dfs2(x) ;
            low[k] = min(low[x],low[k]) ;
            if (low[x] >= niv[k])
            {
                nr2 = 0 ;
                do
                {

                        var = st.size()-1;
                        a1 = st[var].first;
                        a2 = st[var].second;
                        sol[++nr2] = a1;
                        sol[++nr2] = a2;
                        st.pop_back() ;
                } while (!st.empty() && !((a1==x && a2==k)  || (a1==k && a2==x)));
            }
            sort(sol+1,sol+nr2+1) ;
            for (int j = 1 ; j <= nr2 ; ++j)
                if (sol[j] != sol[j-1]) g << sol[j] << ' ' ;
            g << '\n';
        }
        else if (x != t[k]) low[k] = min (low[k] , niv[x]) ;
    }
}
int main()
{
    int x, y;
    f >> N >> M ;
    for (int i = 1 ; i <= M ; ++i)
    {
        f >> x >> y;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
    }
        niv[1] = 1 ;
            dfs(1); // ptr aflare componente biconexe
        g << nr << '\n';
        reinitializare();

        niv[1] = 1;
        dfs2(1) ;
        return 0;
}