Cod sursa(job #1810294)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 19 noiembrie 2016 21:11:18
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000 + 1;

vector<int> BCC[MAX_N];
vector<int> G[MAX_N];

int low[MAX_N], dfn[MAX_N];
stack<pair<int,int>, vector<pair<int,int>>> stiva;

int N, M;
int NR_BCC;

void biconex(int x, int y){
    NR_BCC++;
    pair<int,int> p = {x, y}, q;

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

        BCC[NR_BCC].push_back(q.first);
        BCC[NR_BCC].push_back(q.second);

    } while (p != q);
}

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

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

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

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

    in >> N >> M;

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

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

    dfs(1, 1);

    out << NR_BCC << "\n";

    for (int i = 1; i <= NR_BCC; i++){
        sort(BCC[i].begin(), BCC[i].end());
        BCC[i].erase(unique(BCC[i].begin(), BCC[i].end()), BCC[i].end());

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

        out << "\n";
    }

    return 0;
}