Cod sursa(job #1862486)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 29 ianuarie 2017 23:29:20
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMax = 1e5 + 5;

vector < int > G[NMax];
stack < pair < int, int > > Stack;
vector < vector < int > > Ans;

int level[NMax];
int low[NMax];

inline void AddComponent(const int &a, const int &b) {
    vector < int > aux;

    int x, y;
    do {
        x = (Stack.top()).first;
        y = (Stack.top()).second;
        aux.push_back(x);
        aux.push_back(y);
        Stack.pop();
    } while(x != a || y != b);

    Ans.push_back(aux);
}

void DFS(const int &node, const int &lvl) {

    level[node] = low[node] = lvl;
    for(auto const &i: G[node]) {
        if(level[i] == 0) {
            Stack.push({node, i});
            DFS(i, lvl + 1);
            low[node] = min(low[node], low[i]);
            if(low[i] >= level[node]) {
                AddComponent(node, i);
            }
        } else {
            low[node] = min(low[node], level[i]);
        }
    }

}

int main() {
    ios::sync_with_stdio(false);

    int n, m;
    fin >> n >> m;

    for(int i = 1; i <= m; i++) {
        int x, y;
        fin >> x >> y;

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

    DFS(1, 1);

    fout << Ans.size() << "\n";
    for(auto i: Ans) {
        sort(i.begin(), i.end());
        i.erase(unique(i.begin(), i.end()), i.end());
        for(auto const &j: i) {
            fout << j << " ";
        }

        fout << "\n";
    }

    return 0;
}