Cod sursa(job #1301136)

Utilizator pop_bogdanBogdan Pop pop_bogdan Data 25 decembrie 2014 17:08:37
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <fstream>
#include <stack>
#include <vector>
#include <cstring>
using namespace std;

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

#define DIM 100001

int N, M, x, y, actualLevel(1), Ans;
int minLevel[DIM], Level[DIM];
bool Vis[DIM];
vector <int> V[DIM];
vector < vector <int> > Sol;
stack <int> S;

void Input();
void DFS(int);
void BC(int);

int main()
{
    Input();
    DFS(1);
    memset(Vis,0,sizeof(Vis));
    BC(1);
    os << Sol.size() << '\n';
    for ( int i = 0; i < Sol.size(); ++i )
    {
        for ( int j = 0; j < Sol[i].size(); ++j )
            os << Sol[i][j] << " ";
        os << '\n';
    }

    is.close();
    os.close();
}

void Input()
{
    is >> N >>  M;
    for ( int i = 1; i <= N; ++i )
        minLevel[i] = 0x3f3f3f3f;
    for ( int i = 1; i <= M; ++i )
    {
        is >> x >> y;
        V[x].push_back(y);
        V[y].push_back(x);
    }
}

void DFS(int x)
{
    actualLevel++;
    Vis[x] = 1; Level[x] = actualLevel;
    vector <int> :: iterator it  = V[x].begin();

    for ( it = V[x].begin() ; it != V[x].end(); ++it )
    {
        if ( !Vis[(*it)] )
        {
            DFS(*it);
            minLevel[x] = min(minLevel[x],minLevel[*it]);
        }
        else
            minLevel[x] = min(minLevel[x],Level[*it]);
    }
    actualLevel--;

}

void BC(int x)
{
    Vis[x] = 1;
    S.push(x);
        vector <int> :: iterator it;
    for ( vector <int> :: iterator it  = V[x].begin(); it != V[x].end(); ++it )
    {
        if ( Vis[*it] ) continue;
        BC(*it);
        if ( minLevel[*it] >= Level[x] )
        {
            Ans++;
            Sol.resize(Sol.size() + 1);
            while ( !S.empty() && S.top() != *it )
            {
                Sol[Sol.size() - 1].push_back(S.top());
                S.pop();
            }
            Sol[Sol.size() - 1].push_back(S.top());
            S.pop();
            Sol[Sol.size() - 1].push_back(x);

        }
    }
}