Cod sursa(job #1503502)

Utilizator armandpredaPreda Armand armandpreda Data 16 octombrie 2015 12:55:51
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>

using namespace std;

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

const int LIM=100001;
int n, m, low[LIM], viz[LIM], nr_sol;
vector <int> gr[LIM], sol[LIM];
stack < pair <int, int> > s;
void dfs(int nod, int niv, int tata)
{
    low[nod]=viz[nod]=niv;
    for(int i=0; i<gr[nod].size(); ++i)
    {
        int fiu=gr[nod][i];
        if(fiu==tata) continue;
        if(!low[fiu])
        {
            s.push({nod, fiu});
            dfs(fiu, niv+1, nod);
            low[nod]=min(low[nod], low[fiu]);
            if(low[fiu]>=niv)
            {
                nr_sol++;
                int gata=0;
                while(!s.empty() and !gata)
                {
                    sol[nr_sol].push_back(s.top().first);
                    sol[nr_sol].push_back(s.top().second);
                    if(s.top().first==nod and s.top().second==gr[nod][i])
                        gata=1;
                    s.pop();
                }
            }
        }
        else
            low[nod]=min(low[nod], viz[fiu]);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        int x, y;
        cin>>x>>y;
        gr[x].push_back(y);
        gr[y].push_back(x);
    }
    dfs(1, 1, 0);
    cout<<nr_sol<<'\n';
    memset(viz, 0, sizeof(viz));
    for(int i=1; i<=nr_sol; ++i)
    {
        for(int j=0; j<sol[i].size(); ++j)
            if(viz[ sol[i][j] ]!=i)
            {
                cout<<sol[i][j]<<' ';
                viz[ sol[i][j] ]=i;
            }
        cout<<'\n';
    }
    return 0;
}