Cod sursa(job #843829)

Utilizator IoannaPandele Ioana Ioanna Data 28 decembrie 2012 15:08:22
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include<fstream>
#include<bitset>
#include<vector>
#include<stack>
#define MMAX 200002
#define NMAX 100002
using namespace std;

stack <int> s;
vector <int> v[NMAX],comp[NMAX];
int n,m;
bitset <NMAX> viz;
int lowl[NMAX],level[NMAX],t[NMAX],nr=1;

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

void scan()
{
    int a,b;
    in>>n>>m;
    for (int i=1;i<=m;i++)
    {
        in>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
}

void componenta(int nod)
{
    int a;
    viz.reset();
    while (s.top()!=nod)
    {
        a=s.top();
        if (viz[a]==false)
        {
            comp[nr].push_back(a);
            viz[a]=true;
        }
        s.pop();
    }
    if (viz[nod]==false)
    {
        comp[nr].push_back(nod);

    }
    nr++;
}

void dfs(int nod,int lvl)
{
    level[nod]=lvl;
    lowl[nod]=lvl;
    s.push(nod);
    for(vector<int>::iterator it=v[nod].begin(); it!=v[nod].end();++it)
    {
        if (!level[*it])
        {
            s.push(nod);
            t[*it]=nod;
            dfs(*it,lvl+1);
            if (lowl[*it]<lowl[nod])
                lowl[nod]=lowl[*it];

            if (level[nod]<=lowl[*it])
            {
                componenta(nod);
            }
        }
        else if (t[nod]!=*it)
        {
            if (level[*it]<lowl[nod])
            lowl[nod]=level[*it];
        }
    }


}

void print()
{
    int l;
    vector <int>::iterator it;
    out<<nr-1<<"\n";
    nr--;
    for(int l=1;l<=nr;l++)
    {
        for (it=comp[l].end()-1;it!=comp[l].begin();it--)
            out<<*it<<" ";
        out<<*it<<"\n";
    }
}
int main()
{
    scan();
    for (int i=1;i<=n;i++)
    {
            if (!viz[i])
            {
                dfs(i,1);
            }

    }
    print();
    return 0;
}