Cod sursa(job #2113978)

Utilizator felixiPuscasu Felix felixi Data 25 ianuarie 2018 12:20:47
Problema Componente biconexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.23 kb
#include<bits/stdc++.h>

using namespace std;

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

const int NMAX = 100000;

stack<pair<int,int>> stk;
vector<int> G[NMAX+2];
int N, M, dfn[NMAX], low[NMAX+2];
vector<int> my_comp;
vector<vector<int>> bicon;

inline void normalize(vector<int>& vec)
{
    sort(vec.begin(), vec.end());
    vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
}

void another_one(int x, int y)
{
    my_comp.clear();
    int lx, ly;
    do {
        auto pp = stk.top();
        lx = pp.first;
        ly = pp.second;
        my_comp.push_back(lx);
        my_comp.push_back(ly);
        stk.pop();
    }
    while( !stk.empty() && !(lx == x && ly == y) );
    bicon.push_back(my_comp);
}
bool viz[NMAX+2];
void dfs2(int nod, int tata)
{
    viz[nod] = 1;
    for( auto x : G[nod] ) {
        if( x == tata ) continue;

        if( !viz[x] )
            dfs2(x, nod);

        if( low[x] >= dfn[nod] ) cerr << nod << ' ' << x << '\n';
    }
}

void print_stiva()
{
    vector<pair<int,int>> vec;
    while( !stk.empty() ) {
        vec.push_back(stk.top());
        stk.pop();
    }
    for( int i = vec.size() - 1;  i >= 0;  --i ) {
     ///   cerr << vec[i].first << ' ' << vec[i].second << '\n';
        stk.push(vec[i]);
    }
}

void dfs(int nod, int tata, int time)
{
    ///cerr << "stiva @ " << nod << '\n';
    ///print_stiva();
    dfn[nod] = low[nod] = time;
    for( const auto& x : G[nod] ) {
        if( x == tata ) continue;
        if( dfn[x] == 0 ) {
            stk.push({nod, x});
            dfs(x, nod, time + 1);
            low[nod] = min(low[nod], low[x]);
            if( low[x] >= dfn[nod] )
                another_one(nod, x);
        }
        else {
            low[nod] = min(low[nod], low[x]);
        }
    }
}

int main()
{
    in >> N >> M;
    for( int i = 1;  i <= M;  ++i ) {
        int x,y;
        in >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(min(N, 2), -1, 1);
   /// dfs2(2, -1);
    out << bicon.size()<< '\n';
    for( auto & ln : bicon )  {
        normalize(ln);
        for( const auto & x : ln ) out << x << ' ';
        out << '\n';
    }
    return 0;
}