Cod sursa(job #1864315)

Utilizator filip.mihalutMihalut Filip filip.mihalut Data 31 ianuarie 2017 18:15:33
Problema Componente biconexe Scor 84
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <bitset>
#include <vector>
#include <algorithm>
#define dim  100005

using namespace std;

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

stack < pair < int,int > > st;
bitset < dim > viz;
vector < vector < int > > lista;
vector < int > gr[dim];
int low[dim],niv[dim],k,n,m,i,x,y;

inline void adaugaComponenta(int x,int y)
{
    k++;
    vector < int > new_vec;
    int xx = 0 ,yy = 0;
    while(x != xx || y != yy) // ajung la muchia critica
    {
        xx = st.top().first;
        yy = st.top().second;
        new_vec.push_back(xx);
        new_vec.push_back(yy);
        st.pop();
    }
    sort(new_vec.begin(),new_vec.end());
    lista.push_back(new_vec);
}

inline void dfs(int nod,int nivel)
{
    int val = 0;
    if(not st.empty())
        val = st.top().second;
    low[nod] = nivel;
    viz [nod] = true;
    int l = gr[nod].size();
    for(int i = 0; i < l; i++)
        if(not viz[gr[nod][i]])
        {
            int new_nod = gr[nod][i];
            st.push( {new_nod , nod});
            dfs(new_nod,nivel + 1);
            low[nod] = min(low[nod],low[ new_nod ]);
            if(low[new_nod] >= nivel)
                adaugaComponenta(new_nod,nod);
        }
        else if(gr[nod][i] != val) low[nod] = min(low[gr[nod][i]],low[nod]);
}

int main()
{
    ios::sync_with_stdio(false);
    f >> n >> m;

    for(i = 1; i <= m; i++)
    {
        f >> x >> y;
        gr[x].push_back(y);
        gr[y].push_back(x);
    }

    dfs(1,1);

    g << k << '\n';

    vector < int > :: iterator it;

    for(i = 0; i < k; i++)
    {
        for(it = lista[i].begin(); it != lista[i].end(); it++)
            if(*it != *(it + 1))
                g << *it << " ";
        g << '\n';
    }
    return 0;
}