Cod sursa(job #1819613)

Utilizator ade_tomiEnache Adelina ade_tomi Data 30 noiembrie 2016 18:15:51
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const int nmax = 100003;
int n, m, niv[nmax], l[nmax];
vector <int> v[nmax];
vector < vector <int> > sol;

stack <int > s;
void solve(int x,int y)
{
    vector <int> comp;
    
    while (s.top() != y)
    {
       comp.push_back(s.top());
       s.pop();

    }
    s.pop();
    comp.push_back(x);
    comp.push_back(y);
    sol.push_back(comp);
}
void dfs(int k, int dad, int nivel)
{
    l[k] = niv[k] = nivel;
    for (int i = 0; i < v[k].size(); i++)
    {
        if (v[k][i] == dad)
            continue;
        if (niv[v[k][i]] == 0)
        {
            s.push(v[k][i]);
            dfs(v[k][i], k, nivel + 1);
            
            l[k] = min (l[k], l[v[k][i]]);
            if (l[v[k][i]] >= niv[k])
            {
                solve(k, v[k][i]);
            }
        }
        else l[k] = min (l[k], niv[v[k][i]]);
    }
}
int main ()
{
    int x, y;
    ifstream cin ("biconex.in");
    ofstream cout ("biconex.out");
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1, 0, 1);
    cout << sol.size() << "\n";
    for (int i = 0; i < sol.size(); i++)
    {
        sort(sol[i].begin(), sol[i].end());
        sol[i].erase(unique(sol[i].begin(), sol[i].end()), sol[i].end());
        for (int j = 0; j < sol[i].size(); j++)
            cout << sol[i][j] << " ";
         cout << "\n";
    }
    return 0;
}