Cod sursa(job #1414102)

Utilizator rares96cheseliRares Cheseli rares96cheseli Data 2 aprilie 2015 12:57:45
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.94 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");

int N, M, x, y, dad[100005], low[100005], found[100005], order;
vector < int > G[100005], Part;
vector< vector<int> > BCC;
vector < pair <int, int> > st, CE;

template <class T>
inline void elimdupli(vector< T > &v)
{
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}

void getbcc(pair<int, int> M)
{
    vector<int> newbcc; newbcc.clear();
    pair < int, int > E;
    do
    {
        E=st.back(); st.pop_back();
        newbcc.push_back(E.first); newbcc.push_back(E.second);
    } while (E!=M);
    elimdupli(newbcc);
    BCC.push_back(newbcc);
}

void dfs(int nod)
{
    int sons=0;
    low[nod]=found[nod]=++order;
    vector<int>::iterator it=G[nod].begin();

    for (; it!=G[nod].end(); ++it)
        if (!dad[*it])
        {
            ++sons; dad[*it]=nod; st.push_back(make_pair(nod, *it));
            dfs(*it); low[nod]=min(low[nod], low[*it]);

            if (low[*it]>=found[nod])
                getbcc(make_pair(nod, *it));

            if (low[*it]>=found[nod] && dad[nod]!=nod)
                Part.push_back(nod);

            if (low[*it]>found[nod])
                CE.push_back(make_pair(nod, *it));
        }
        else if (dad[nod]!=*it)
            low[nod]=min(low[nod], found[*it]);

    if (dad[nod]==nod && sons>1)
        Part.push_back(nod);
}

void solve()
{
    dad[1]=1; dfs(1);
    elimdupli(Part);
    elimdupli(CE);
}

void printbcc()
{
    g<<BCC.size()<<'\n';
    for (int i=0; i<(int)BCC.size(); ++i)
    {
        for (int j=0; j<(int)BCC[i].size(); ++j)
            g<<BCC[i][j]<<' '; g<<'\n';
    }
}

int main()
{
    f>>N>>M;
    for (int i=1; i<=M; ++i)
    {
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    solve();
    printbcc();
    return 0;
}