Cod sursa(job #2663225)

Utilizator DeliaGhergheGherghe Ioana-Delia DeliaGherghe Data 25 octombrie 2020 17:13:02
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;
vector <int> l[100001];
int N, M, low[100001],nodet[100001];
int timp;
stack <pair <int, int> > st;
vector <vector <int> > sol;

void create_comp(int i, int j)
{
    vector <int> new_comp;
    int x,y;
    do
    {
        x = st.top().first;
        y = st.top().second;
        st.pop();
        new_comp.push_back(x);
        new_comp.push_back(y);
    } while (x != i || y != j);
    sol.push_back(new_comp);
}

void DFS(int nod, int t)
{
    nodet[nod] = timp;
    low[nod] = timp;

    for (int i = 0; i < l[nod].size(); i++)
    {
        if (l[nod][i] != t && nodet[l[nod][i]] == -1)
        {
            st.push({nod, l[nod][i]});
            timp++;
            DFS(l[nod][i], nod);
            low[nod] = min(low[nod], low[l[nod][i]]);
            if (nodet[nod] <= low[l[nod][i]])
            {
                create_comp(nod, l[nod][i]);
            }
        }
        else if(nodet[l[nod][i]] != -1)
        {
            low[nod] = min(low[nod], nodet[l[nod][i]]);
        }
    }
}

int main()
{
    ifstream fin("biconex.in");
    ofstream fout("biconex.out");

    fin >> N >> M;
    int i,j,k;

    for (i = 0; i < M; i++)
    {
        fin >> j >> k;
        l[j].push_back(k);
        l[k].push_back(j);
    }

    for (i = 1; i <= N; i++)
        nodet[i] = -1;

    DFS(1, 0);

    fout << sol.size() << "\n";

    for (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 (j = 0; j < sol[i].size(); j++)
            fout << sol[i][j] << " ";
        fout << "\n";
    }


    return 0;
}