Cod sursa(job #1378787)

Utilizator oprea1si2si3Oprea Sebastian oprea1si2si3 Data 6 martie 2015 14:18:58
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int kNMax = 100010;
int n, nr_sol, nivel[kNMax], adn[kNMax];
stack<pair<int,int> > Stack;
vector<int> G[kNMax], sol[kNMax];


void Citire() {
    ifstream in("biconex.in");
    int m, x, y;
    in >> n >> m;
    for (int i = 1; i <= m; ++i) {
        in >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    in.close();
}

void Dfs(int nod, int tata) {
    nivel[nod] = nivel[tata] + 1;
    adn[nod] = nivel[nod];
    for (int i = 0; i < G[nod].size(); ++i) {
        int vecin = G[nod][i];
        if (vecin != tata) {
            if (nivel[vecin] == 0) {
                Stack.push(make_pair(nod, vecin));
                Dfs(vecin, nod);
                if (adn[vecin] >= nivel[nod]) {
                    int x = Stack.top().first;
                    int y = Stack.top().second;
                    Stack.pop();
                    sol[++nr_sol].push_back(y);
                    while (nod != x && vecin != y) {
                        x = Stack.top().first;
                        y = Stack.top().second;
                        Stack.pop();
                        sol[nr_sol].push_back(y);
                    }
                    sol[nr_sol].push_back(x);
                }

            }
            adn[nod] = min(adn[nod], adn[vecin]);
        }
    }
}


void Afisare() {
    ofstream out("biconex.out");
    out << nr_sol << '\n';
    for (int i = 1; i <= nr_sol; ++i) {
        for (int j = 0; j < sol[i].size(); ++j)
            out << sol[i][j] << ' ';
        out << '\n';
    }
    out.close();
}

int main() {
    Citire();
    Dfs(1, 0);
    Afisare();
    return 0;
}