Cod sursa(job #1391123)

Utilizator dorumusuroiFMI - Doru Musuroi dorumusuroi Data 17 martie 2015 17:32:32
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.38 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <utility>
#include <algorithm>
using namespace std;

const int dim = 100005;

ifstream f("biconex.in");
ofstream g("biconex.out");
pair<int,int> muchie;

vector < pair<int, int> > muchii;

vector <int> vf[dim];
stack < vector<int> > comp_bicon;

int viz[dim], nv[dim], L[dim], t[dim], crit[dim];
int n, m, nr, rad;
//int bicon;

void citeste_graf()
{
    int a,b;
    f>>n>>m;
    for(int i = 0; i < m; i++)
        {
            f>>a>>b;
            vf[a].push_back(b);
            vf[b].push_back(a);
        }
}

void DF(int nod)
{
    int nod2;
    viz[nod] = 1;
    L[nod] = nv[nod];
    int nr_noduri = vf[nod].size();
    for(int i = 0; i < nr_noduri; i++)
    {
        nod2 = vf[nod][i];
        if(!viz[nod2])
        {
            muchie = make_pair(nod, nod2);
            muchii.push_back(muchie);
            nv[nod2] = nv[nod] +1;
            t[nod2]=nod;
            if(nod == rad)
                nr++;
            DF(nod2);

            if(L[nod] > L[nod2])
                L[nod] = L[nod2];
            if(L[nod2] >= nv[nod])
                {
                    crit[nod] = 1;
                    vector <int> v;
                    do
                    {
                        muchie = muchii.back();
                        v.push_back(muchie.first), v.push_back(muchie.second);
                        muchii.pop_back();
                    }while(muchie.first != nod && muchie.second != nod2);
                    comp_bicon.push(v);
                }

        }
        else
            if(nod2 != t[nod] && L[nod] > nv[nod2])
                L[nod] = nv[nod2];
    }
}
int main()
{
    citeste_graf();
    for(int i = 1; i <= n; i++)
        if(!viz[i])
        {
            nv[i] = 1;
            rad = i;
            nr = 0;
            DF(i);
            crit[rad] = nr >1;
        }
    g<<comp_bicon.size()<<'\n';
    while(!comp_bicon.empty())
    {
        vector<int> v;
        int el;
        v = comp_bicon.top();
        comp_bicon.pop();
        sort(v.begin(), v.end());
        el = v[0];
        g<<el<<' ';
        for(int i = 1; i < v.size(); i++)
            if(v[i]!=el)
            {
                g<<v[i]<<' ';
                el = v[i];
            }
        g<<'\n';
    }

    return 0;
}