Cod sursa(job #1728281)

Utilizator ValentinSavoiuFMI Savoiu Valentin-Marian ValentinSavoiu Data 12 iulie 2016 17:32:56
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,i,j,x,y,viz[100001],H[100001];
vector <int> G[100001],comp;
vector <vector <int>> bic;
stack <int> St;
void dfs(int nod,int h)
{
    int v,hh,i;
    H[nod]=h;
    viz[nod]=1;
    St.push(nod);
    hh=h;
    for (i=0;i<G[nod].size();i++)
    {
        v=G[nod][i];
        if(viz[v])  hh=min(hh,H[v]);
        else
        {
            dfs(v,h+1);
            hh=min(hh,H[v]);
            if(H[v]==h)
            {
                comp.clear();
                while(St.top()!=v)
                {
                    comp.push_back(St.top());
                    St.pop();
                }
                comp.push_back(St.top());
                St.pop();
                comp.push_back(nod);

                bic.push_back(comp);
            }
        }
    }
    H[nod]=hh;
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(i=1;i<=n;i++)
        if(viz[i]==0)
            dfs(i,0);
    g<<bic.size()<<'\n';
    for(i=0;i<bic.size();i++)
    {
        for(j=0;j<bic[i].size();j++) g<<bic[i][j]<<' ';
        g<<'\n';
    }
    return 0;
}