Cod sursa(job #1451533)

Utilizator flore77Simion Florentin flore77 Data 17 iunie 2015 14:50:31
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.75 kb
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
#include <algorithm>
using namespace std;

#define NMAX 100100
#define UNDEFINED 0

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

vector<int> graph[NMAX];
vector<vector<int> > solution;
stack<pair<int, int> > s;
int idx[NMAX];
int lowlink[NMAX];
int parent[NMAX];
int index, nodes;

inline void initParent() {
    for (int i = 0; i < nodes; i++)
        parent[i] = -1;
}

inline void printSolution() {
    vector<int> sol;

    while (!s.empty()) {
        sol.push_back(s.top().first);
        sol.push_back(s.top().second);
        s.pop();
    }
    solution.push_back(sol);

    out << solution.size() << "\n";

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

        for (unsigned int j = 0; j < solution[i].size(); j++) {
            out << solution[i].at(j) + 1 << " ";
        }
        out << "\n";
    }
}

inline void addSolution(pair<int, int> p) {
    vector<int> sol;

    while (s.top() != p) {
        sol.push_back(s.top().first);
        sol.push_back(s.top().second);
        s.pop();
    }

    sol.push_back(s.top().first);
    sol.push_back(s.top().second);
    s.pop();

    solution.push_back(sol);
}

void dfsAp(int start) {
    index++;

    int children = 0;

    idx[start] = lowlink[start] = index;

    for (unsigned int i = 0; i < graph[start].size(); i++) {
        int neighbour = graph[start].at(i);



        if (idx[neighbour] == UNDEFINED) {
            s.push(make_pair(start, neighbour));
            children++;
            parent[neighbour] = start;
            dfsAp(neighbour);
            lowlink[start] = min(lowlink[start], lowlink[neighbour]);

            if (parent[start] == -1 && children > 1) {
                addSolution(make_pair(start, neighbour));
            }

            if (parent[start] != -1 && lowlink[neighbour] >= idx[start]) {
                addSolution(make_pair(start, neighbour));
            }
        }
        else if (neighbour != parent[start]) {
            lowlink[start] = min(lowlink[start], idx[neighbour]);
        }
    }
}

void ArticulationPoints() {
    initParent();

    index = 0;

    for (int i = 0; i < nodes; i++) {
        if (idx[i] == UNDEFINED)
            dfsAp(i);
    }

    printSolution();
}


int main() {
    int edges, x, y;

    in >> nodes >> edges;

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

        graph[x - 1].push_back(y - 1);
        graph[y - 1].push_back(x - 1);
    }

    ArticulationPoints();

    return 0;
}