Cod sursa(job #757199)

Utilizator BitOneSAlexandru BitOne Data 11 iunie 2012 14:08:21
Problema Componente biconexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <stack>
#include <bitset>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>

using namespace std;
typedef pair<int, int> pr;

const int N_MAX=100011;

stack<pr> S;
bitset<N_MAX> was;
vector<int> G[N_MAX], CBC[N_MAX];
int index, cbcSize;
int dfsIndex[N_MAX], lowIndex[N_MAX];

inline int _min(int x, int y) {return x <= y ? x : y;}
inline void DFS(int x)
{
    dfsIndex[x]=lowIndex[x]=++index;
    vector<int>::const_iterator it=G[x].begin(), iend=G[x].end();
    for(; it < iend; ++it)
        if(0 == dfsIndex[*it])
        {
            S.push(pr(x, *it));
            DFS(*it);
            lowIndex[x]=_min(lowIndex[x], lowIndex[*it]);
            if(lowIndex[*it] >= dfsIndex[x])
            {
                static pr y, z;
                y.first=x; y.second=*it;
                do {
                        z=S.top(); S.pop();
                        if(false == was.test(z.first))
                            CBC[cbcSize].push_back(z.first), was.set(z.first);
                        if(false == was.test(z.second))
                            CBC[cbcSize].push_back(z.second), was.set(z.second);
                   }while(y != z);
                ++cbcSize;
            }
            was&=0;
        }
        else lowIndex[x]=_min(lowIndex[x], dfsIndex[*it]);
}
int main()
{
    int N, M, x, y, i;
    ifstream in("biconex.in");
    ofstream out("biconex.out");

    for(in>>N>>M; M; --M)
    {
        in>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(x=1; x <= N; ++x)
        if(0 == dfsIndex[x])
            DFS(x);
    out<<cbcSize<<'\n';
    for(i=0; i < cbcSize; ++i)
    {
        copy(CBC[i].begin(), CBC[i].end(), ostream_iterator<int>(out, " "));
        out<<'\n';
    }
    return EXIT_SUCCESS;
}