Cod sursa(job #1503487)

Utilizator armandpredaPreda Armand armandpreda Data 16 octombrie 2015 12:03:30
Problema Componente biconexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

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

const int LIM=100001, ARB=1, INT=2;
int n, m, low[LIM], nr_sol;
struct muc
{
    int a, b, cod;
}v[LIM+LIM];
vector <int> gr[LIM], sol[LIM];
stack <int> s;
char viz[LIM];
void dfs(int nod, int niv)
{
    low[nod]=niv;
    for(int i=0; i<gr[nod].size(); ++i)
    {
        int fiu=v[ gr[nod][i] ].a;
        if(fiu==nod) fiu=v[ gr[nod][i] ].b;
        if(!v[ gr[nod][i] ].cod)
            if(!low[fiu])
                v[ gr[nod][i] ].cod=ARB;
            else
                v[ gr[nod][i] ].cod=INT;
        if(v[ gr[nod][i] ].cod==ARB and low[fiu]) continue;
        if(v[ gr[nod][i] ].cod==ARB and !low[fiu])
        {
            s.push(gr[nod][i]);
            dfs(fiu, niv+1);
        }
        if(v[ gr[nod][i] ].cod==INT)
            low[nod]=min(low[nod], low[fiu]);
        if(v[ gr[nod][i] ].cod==ARB and low[fiu]>=low[nod])
        {
            nr_sol++;
            bool gata=0;
            while(!s.empty() and !gata)
            {
                if(s.top()==gr[nod][i]) gata=1;
                sol[nr_sol].push_back(v[s.top()].a);
                sol[nr_sol].push_back(v[s.top()].b);
                s.pop();
            }
        }
        low[nod]=min(low[nod], low[fiu]);

    }
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        cin>>v[i].a>>v[i].b;
        gr[v[i].a].push_back(i);
        gr[v[i].b].push_back(i);
    }
    dfs(1, 1);
    cout<<nr_sol<<'\n';
    for(int i=1; i<=nr_sol; ++i)
    {
        for(int j=0; j<sol[i].size(); ++j)
            if(!viz[ sol[i][j] ])
            {
                cout<<sol[i][j]<<' ';
                viz[ sol[i][j] ]=1;
            }
        for(int j=0; j<sol[i].size(); ++j)
            viz[ sol[i][j] ]=0;
        cout<<'\n';
    }
    return 0;
}