Cod sursa(job #1415519)

Utilizator diana97Diana Ghinea diana97 Data 4 aprilie 2015 22:24:46
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

ifstream f ("biconex.in");
ofstream g ("biconex.out");

const int NMAX = 100000 + 1;

int n, m, nrcomp;
int index_crt;
int niv[NMAX];
vector <int> graf[NMAX], comp[NMAX];
stack <int> st;


void citeste() {
    int a, b;
    f >> n >> m;
    for (int i = 1; i <= m; i++) {
        f >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
}


int DFS(int nod, int nivel, int tata) {
    int h, h2;
    niv[nod] = h = nivel;

    st.push(nod);
    int fiu, l = graf[nod].size();

    for (int i = 0; i < l; i++) {
        fiu = graf[nod][i];
        if (fiu == tata) continue;
        if (!niv[fiu]) {
            h2 = DFS(fiu, nivel + 1, nod);
            if (h2 >= niv[nod]) {
                comp[++nrcomp].push_back(nod);
                while (st.top() != nod) {
                    comp[nrcomp].push_back(st.top());
                    st.pop();
                }
            }
            h = min(h, h2);
        }
        else h = min(h, niv[fiu]);
    }
    return h;
}


void scrie() {
    int a, b;
    g << nrcomp << '\n';
    for (int i = 1; i <= nrcomp; i++) {
        b = comp[i].size();
        for (int j = 0; j < b; j++) g << comp[i][j] << ' ';
        g << '\n';
    }
}


int main() {
    citeste();
    DFS(1, 1, 0);
    scrie();

}