Cod sursa(job #2092191)

Utilizator infomaxInfomax infomax Data 21 decembrie 2017 12:01:17
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <bitset>
#include <vector>
#include <stack>

using namespace std;

ifstream F("biconex.in");
ofstream G("biconex.out");

int n, m, niv[100005], low[100005], x, y, k;
bitset<100005> v;
stack<int> st;
vector<int> a[100005], ans[100005];

void dfs( int nod, int tata, int Niv )
{
    v[ nod ] = 1;
    niv[ nod ] = Niv;
    low[ nod ] = Niv;
    st.push(nod);
    vector<int> :: iterator it;
    for( it = a[nod].begin(); it != a[nod].end(); ++ it )
    {
        if( *it == tata ) continue;
        if( v[*it] )
        {
            low[nod] = min(low[nod], niv[*it]);
            continue;
        }
        dfs( *it, nod, Niv + 1 );
        low[nod] = min(low[nod], low[*it]);
        if( low[*it] >= niv[nod] )
        {
            ++ k;
            do
            {
                x = st.top();
                st.pop();
                ans[k].push_back(x);
            }while( x != *it );
            ans[k].push_back(nod);
        }

    }
}

int main()
{
    F >> n >> m;
    for( int i = 1; i <= m; ++ i )
    {
        F >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs( 1, 0, 1 );
    G << k << '\n';
    vector<int> :: iterator it;
    for(int i = 1; i <= k; ++ i, G << '\n')
        for( it = ans[i].begin(); it != ans[i].end(); ++ it )
            G << *it << " ";
    return 0;
}