Cod sursa(job #1168754)

Utilizator CostinVFMI CostinVictorGabriel CostinV Data 9 aprilie 2014 14:46:02
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include<fstream>
#include<vector>
#include<stack>

using namespace std;

int *niv[2], k;
stack <int> *com;
stack <pair<int, int> > comp;
vector <int> *g;
bool *viz;

void dfs (int x, int n)
{
    viz[x]=1;
    niv[0][x] = n;
    niv[1][x] = n;

    for(int i = 0; i<g[x].size(); i++)
    {
        if(!viz[g[x][i]])
        {
            comp.push(make_pair(x, g[x][i]));
            dfs(g[x][i], n+1);

            if(niv[0][x] <= niv[1][g[x][i]])
            {
                for(;;)
                {
                    com[k].push(comp.top().second);
                    if(comp.top().first==x)
                        break;
                    comp.pop();
                }
                com[k].push(x);
                comp.pop();
                k++;
            }

            niv[1][x] = min (niv[1][x], niv[1][g[x][i]]);
        }
        else
            niv[1][x] = min (niv[1][x], niv[0][g[x][i]]);
    }
}

int main()
{
    int n, m, x, y;

    ifstream f("biconex.in");
    f>>n>>m;

    g = new vector<int> [n];
    viz = new bool [n];
    niv[0] = new int [n];
    niv[1] = new int [n];
    com = new stack<int> [n];

    for(int i=0; i<m; i++)
    {
        f>>x>>y;
        g[x-1].push_back(y-1);
        g[y-1].push_back(x-1);
    }


    dfs(0, 0);

    ofstream o("biconex.out");
    o<<k<<"\n";

    for(int i=0; i<k; i++)
    {
        while(!com[i].empty())
        {
            o<<com[i].top()+1<<" ";
            com[i].pop();
        }
        o<<"\n";
    }

    return 0;
}