Cod sursa(job #1537226)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 27 noiembrie 2015 01:27:20
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000 + 1;
const int MAX_M = 200000 + 1;

stack< pair<int,int> > stiva;
vector<vector<int>>BC;
vector<int> G[MAX_N];

int lowLink[MAX_N];
int dfn[MAX_N];

int N, M;

void biconex(int x, int y)
{
    vector<int> v;
    pair<int,int> p;

    do
    {
        p = stiva.top();
        stiva.pop();

        v.push_back(p.first);
        v.push_back(p.second);

    } while (p.first != x || p.second != y);

    BC.push_back(v);
}

void dfs(int node, int nr)
{
    lowLink[node] = dfn[node] = nr;

    for (int son : G[node])
    {
        if (dfn[son] == 0)
        {
            stiva.push({node, son});
            dfs(son, nr + 1);

            lowLink[node] = min(lowLink[node], lowLink[son]);

            if (lowLink[son] >= dfn[node])
            {
                biconex(node, son);
            }

        }
        else
            lowLink[node] = min(lowLink[node], dfn[son]);
    }
}

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

    in >> N >> M;

    for (int i = 1; i <= M; ++i)
    {
        int x, y;
        in >> x >> y;

        G[x].emplace_back(y);
        G[y].emplace_back(x);
    }

    for (int i = 1; i <= N; ++i)
        if (dfn[i] == 0)
            dfs(i, 1);

    out << BC.size() << "\n";

    for (auto v : BC)
    {
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());

        for (int x : v)
            out << x << " ";

        out << "\n";
    }

    return 0;
}