Cod sursa(job #1383576)

Utilizator rogoz.bogdanRogoz Bogdan rogoz.bogdan Data 10 martie 2015 13:33:46
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <fstream>
#include <vector>
#define MX 100001
using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m;
vector<int> v[MX], t[MX];
int parent[MX], disc[MX], low[MX], act, total;
bool viz[MX];

struct muchie
{
    int i,j;
};
vector<muchie> d;

void ART(int i)
{
    disc[i] = low[i] = ++act;
    int ch=0;
    muchie u,e;

    vector<int>::iterator it;
    for(it=v[i].begin(); it!=v[i].end(); it++)
    {
        if(!disc[*it])
        {
            ch++;
            parent[*it] = i;
            e.i = i;
            e.j = *it;
            d.push_back(e);
            ART(*it);

            low[i] = min(low[i], low[*it]);
            if(low[*it] >= disc[i])
        {

            //fout<<i<<' ';
            total++;
            t[total].push_back(i);
            while(!d.empty())
            {
                u = d.back();
                d.pop_back();

                //fout<<u.j<<' ';
                t[total].push_back(u.j);
                if(u.i==i && u.j==*it) break;
            }
            //fout<<'\n';
            //break;
        }

        }
        else
        {
            low[i] = min(low[i], disc[*it]);
        }

    }

}

int main()
{
    int i,x,y;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    for(i=1; i<=n; i++)
    {
        if(!disc[i])
        {
            ART(i);
        }
    }

    fout<<total<<'\n';
    vector<int>::iterator it;
    for(i=1; i<=total; i++)
    {
        for(it=t[i].begin(); it!=t[i].end(); it++)
        {
            fout<<*it<<' ';
        }
        fout<<'\n';
    }

    fin.close(); fout.close();
    return 0;
}