Cod sursa(job #2113891)

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

using namespace std;

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

const int NMAX = 100000;

map<pair<int,int>,bool> orient;
vector<int> init[NMAX+2];
bool viz[NMAX+2];
int ctc[NMAX+2], ind_ctc = 0;
vector<int> order, my_comp;
vector<pair<int,bool>> G[NMAX+2];
int N, M;
vector<vector<int>> sol;

void dfs_1(int nod)
{
    viz[nod] = 1;
    for( const auto& x : init[nod] ) {

        if( !orient[{nod,x}] )
            orient[{nod,x}] = orient[{x,nod}] = 1,
            G[nod].push_back({x,1}),
            G[x].push_back({nod,0});

        if( viz[x] ) continue;

        dfs_1(x);
    }
}

void dfs_plus(int nod)
{
    viz[nod] = 1;
    for( const auto& pp : G[nod] ) {
        if( !pp.second ) continue;
        const auto& x = pp.first;
        if( viz[x] ) continue;
        dfs_plus(x);
    }
    order.push_back(nod);
}

void dfs_minus(int nod)
{
    viz[nod] = 1;
    ctc[nod] = ind_ctc;
    my_comp.push_back(nod);
    for( const auto& pp : G[nod] ) {
        if( pp.second ) continue;
        const auto& x = pp.first;
        if( viz[x] ) continue;
        dfs_minus(x);
    }
}

int main()
{

    in >> N >> M;
    for( int i = 1;  i <= M;  ++i ) {
        int x,y;
        in >> x >> y;
        init[x].push_back(y);
        init[y].push_back(x);
    }
    dfs_1(1);

    for( int i = 1;  i <= N;  ++i ) init[i].clear();

    memset(viz, 0, sizeof(viz));
    for( int i = 1;  i <= N;  ++i ) {
        if( !viz[i] )
            dfs_plus(i);
    }
    memset(viz, 0, sizeof(viz));
    reverse(order.begin(), order.end());
    for( auto x : order ) {

        if( !viz[x] ) {
            ++ind_ctc;
            my_comp.clear();
            dfs_minus(x);
            if( my_comp.size() > 1 )
                sol.push_back(my_comp);
        }

    }
    for( int i = 1;  i <= N;  ++i ) {
        for( const auto& pp : G[i] ) {
            if( !pp.second ) continue;

            const auto& x = pp.first;
            if( ctc[x] == ctc[i] ) {
              ///  if( z ) special_comp[ ctc[x] ] = 1;
            }
            else {
                ///adia[ ctc[i] ].push_back({ ctc[x] ,z});
                ///adia[ ctc[x] ].push_back({ ctc[i] ,z});
                sol.push_back({i, x});
            }
        }
    }
    out << sol.size() << '\n';
    for( auto& ln : sol ) {
        for( auto& x : ln ) out << x << ' ';
        out << '\n';
    }
    return 0;
}