Cod sursa(job #1884672)

Utilizator topala.andreiTopala Andrei topala.andrei Data 18 februarie 2017 23:53:54
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");

const int maxn=100005;
int N,M,nrbicon;
int viz[maxn],low[maxn];
vector <int> G[maxn],bicon[maxn];
stack <int> S;
void dfs(int nod,int prec)
{
    int sz=G[nod].size(),i,next;
    viz[nod]=viz[prec]+1;
    low[nod]=viz[nod];
    S.push(nod);
    for (i=0;i<sz;i++)
    {
        next=G[nod][i];
        if (viz[next]==0)
        {
        dfs(next,nod);

        low[nod]=min(low[nod],low[next]);
        if (viz[nod]<=low[next])
        {
            while (S.empty()==0 && S.top()!=next)
            {
                bicon[nrbicon].push_back(S.top());
                S.pop();
            }
            S.pop();
            bicon[nrbicon].push_back(next);
            bicon[nrbicon].push_back(nod);
            nrbicon++;
        }
        }
        else low[nod]=min(low[nod],viz[next]);
    }
}
int main()
{
    int i,j,x,y;
    f>>N>>M;
    for (i=1;i<=M;i++)
    {
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1,0);
    g<<nrbicon<<'\n';
    for (i=0;i<nrbicon;i++)
    {
        for (j=0; j<bicon[i].size(); j++)
        {
            g<<bicon[i][j]<<" ";
        }
        g<<'\n';
    }

}