Cod sursa(job #1168760)

Utilizator CostinVFMI CostinVictorGabriel CostinV Data 9 aprilie 2014 15:05:16
Problema Componente biconexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include<fstream>
#include<vector>
#include<stack>

using namespace std;

int **niv, k;
vector <int> com[1000001];
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_back(comp.top().second);
                    if(comp.top().first==x)
                        break;
                    comp.pop();
                }
                com[k].push_back(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 = new int* [2];
    niv[0]=new int [n];
    niv[1]=new 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].back()+1<<" ";
            com[i].pop_back();
        }
        o<<"\n";
    }

    return 0;
}