Cod sursa(job #1372786)

Utilizator nicol.bolasNicol Bolas nicol.bolas Data 4 martie 2015 15:22:38
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include<fstream>
#include<vector>
#include<set>
using namespace std;
#define NMAX 100005
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector <int> v[NMAX];
set <int> sol[NMAX];
set <int>::iterator it;
pair <int,int> st[NMAX];
int n,m,nr,k,x,y,N[NMAX],L[NMAX];
void dfs(int nod, int niv, int tata)
{
    int i,fiu;
    N[nod]=L[nod]=niv;
    for (i=0;i<v[nod].size();++i)
    {
        fiu=v[nod][i];
        if (fiu==tata) continue;
        if (!N[fiu])
        {
            st[++k]=make_pair(nod,fiu);
            dfs(fiu,niv+1,nod);
            L[nod]=min(L[nod],L[fiu]);
            if (L[fiu]>=N[nod])
            {
                ++nr;
                do
                {
                    sol[nr].insert(st[k].first), sol[nr].insert(st[k].second);
                    --k;
                } while (k>0 && (st[k+1].first!=nod || st[k+1].second!=fiu));
            }
        }
        else
            L[nod]=min(L[nod],N[fiu]);
    }
}
int main()
{
    int i;
    fin>>n>>m;
    for (i=1;i<=m;++i)
    {
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,1,0);
    fout<<nr<<"\n";
    for (i=1;i<=nr;++i)
    {
        for (it=sol[i].begin();it!=sol[i].end();++it)
            fout<<*it<<" ";
        fout<<"\n";
    }
    return 0;
}