Cod sursa(job #2045829)

Utilizator vladm98Munteanu Vlad vladm98 Data 22 octombrie 2017 21:56:23
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include <bits/stdc++.h>
 
using namespace std;
stack <pair<int, int>> solve;
vector <int> graf[100001];
vector <int> componente[100001];
int cate_componente;
int level[100001], minim[100001];
void construieste (int comp, int x, int y)
{
    int a, b;
    while (true)
    {
        a = solve.top().first;
        b = solve.top().second;
        solve.pop();
        if (a == x && b == y)
        {
            componente[comp].push_back(a);
            componente[comp].push_back(b);
            return;
        }
        componente[comp].push_back(a);
        componente[comp].push_back(b);
    }
}
void dfs (int nod, int tata, int nivel)
{
    level[nod] = minim[nod] = nivel;
    for (auto x:graf[nod])
    {
        if (x!=tata)
        {
            if (level[x] == 0)
            {
                solve.push(make_pair(nod, x));
                dfs(x, nod, nivel+1);
                if (minim[x]>=level[nod])
                {
                    ++cate_componente;
                    construieste (cate_componente, nod, x);
                }
                minim[nod] = min(minim[nod], minim[x]);
            }
            else minim[nod] = min(minim[nod], minim[x]);
        }
    }
}
int main()
{
    ifstream fin ("biconex.in");
    ofstream fout ("biconex.out");
    int n, m;
    fin >> n >> m;
    for (int i = 1; i<=m; ++i)
    {
        int x, y;
        fin >> x >> y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    dfs(1, 0, 1);
    fout << cate_componente << '\n';
    for (int i = 1; i<=cate_componente; ++i)
    {
        sort (componente[i].begin(), componente[i].end());
        int vechi = 0;
        for (auto x:componente[i])
            if (x!=vechi)
            {
                vechi = x;
                fout << x << " ";
            }
        fout << '\n';
    }
    return 0;
}