Cod sursa(job #988146)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 22 august 2013 09:16:11
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <vector>

#define inf 100001

using namespace std;

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

vector <int> G[inf],CB[inf];

int stack[inf],lvl[inf];
int n,nrb,a,b,m,t;
bool vis[inf];

int dfs (int x)
{
    vis[x]=1;
    stack[++t] = x;
    int lowlink=inf,child_lowlink;
    lvl[x]=t;

    for (vector <int>::iterator it=G[x].begin();it!=G[x].end(); ++it)
    {
        if (!vis[*it])
        {
            child_lowlink=inf;
            child_lowlink = min (child_lowlink,dfs(*it));
            if (child_lowlink >= lvl[x])
            {
                ++nrb;
                 for (; stack[t]!=*it; --t)
                 {
                     CB[nrb].push_back (stack[t]);
                 }
                 CB[nrb].push_back(stack[t]);
                 --t;
                 CB[nrb].push_back(x);
            }
            lowlink = min (lowlink,child_lowlink);
        }
        else
        {
            lowlink = min (lowlink,lvl[*it]);
        }
    }
    return lowlink;

}

int main()
{
    fin>>n>>m;

    for (int i=1; i<=m; ++i)
    {
        fin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

   // for (int i=1; i<=n; ++i) lvl[i]=inf;

    dfs (1);

    fout<<nrb<<"\n";

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