Cod sursa(job #1519212)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 6 noiembrie 2015 23:49:18
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000 + 1;

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

int lowLink[MAX_N];
int dfn[MAX_N];
bool visited[MAX_N];

int N, M, numberBC;

void biconex(int node, int v)
{
    pair<int,int> p;

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

        BC[ numberBC ].emplace_back(p.first);
        BC[ numberBC ].emplace_back(p.second);

    } while (p.first != node || p.second != v);

    numberBC++;
}

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

    visited[node] = true;

    for (int v : G[node])
    {
        if (visited[v] == 0)
        {
            stiva.push({node, v});
            dfs(v, id + 1);

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

            if (lowLink[v] >= dfn[node])
            {
                biconex(node, v);
            }
        }
        else
            lowLink[node] = min(lowLink[node], dfn[v]);
    }
}

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 (!visited[i])
            dfs(i, 1);

    out << numberBC << "\n";

    for (int i = 0; i < numberBC; ++i)
    {
        sort(BC[i].begin(), BC[i].end());
        BC[i].erase(unique(BC[i].begin(), BC[i].end()), BC[i].end());

        for (int x : BC[i])
            out << x << " ";

        out << "\n";
    }

    return 0;
}