Cod sursa(job #1112617)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 19 februarie 2014 21:31:50
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.17 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

class Graph {
  public:
    static const int NIL = -1;

    Graph(const int _v = 0):
      v(_v),
      edges(vector< vector<int> >(_v, vector<int>())) {}

    int V() const {
        return v;
    }

    vector<int>::const_iterator EdgesBegin(const int x) const {
        return edges[x].begin();
    }

    vector<int>::const_iterator EdgesEnd(const int x) const {
        return edges[x].end();
    }

    void AddEdge(const int x, const int y) {
        edges[x].push_back(y);
        edges[y].push_back(x);
    }

    void GetBiconnectedComponents(vector< vector<int> > &components, vector<int> &criticalVertices, vector< pair<int, int> > &criticalEdges) const {
        vector<int> level = vector<int>(v, -1), minLevel = vector<int>(v, -1);
        for (int x = 0; x < v; ++x) {
            if (level[x] == -1) {
                level[x] = 0;
                vector< pair<int, int> > stack;
                DFS(x, NIL, stack, level, minLevel, components, criticalVertices, criticalEdges);
            }
        }
        sort(criticalVertices.begin(), criticalVertices.end());
        criticalVertices.erase(unique(criticalVertices.begin(), criticalVertices.end()), criticalVertices.end());
    }

    vector< vector<int> > GetBiconnectedComponents() const {
        vector< vector<int> > components;
        vector<int> criticalVertices;
        vector< pair<int, int> > criticalEdges;
        GetBiconnectedComponents(components, criticalVertices, criticalEdges);
        return components;
    }

  private:
    int v;
    vector< vector<int> > edges;

    vector<int> GetComponent(const pair<int, int> &edge, vector< pair<int, int> > &stack) const {
        vector<int> component;
        pair<int, int> topEdge;
        do {
            topEdge = stack.back();
            stack.pop_back();
            component.push_back(topEdge.first);
            component.push_back(topEdge.second);
        } while (topEdge != edge);
        sort(component.begin(), component.end());
        component.erase(unique(component.begin(), component.end()), component.end());
        return component;
    }

    void DFS(const int x, const int father, vector< pair<int, int> > &stack, vector<int> &level, vector<int> &minLevel, vector< vector<int> > &components, vector<int> &criticalVertices, vector< pair<int, int> > &criticalEdges) const {
        minLevel[x] = level[x];
        for (vector<int>::const_iterator y = edges[x].begin(); y != edges[x].end(); ++y) {
            if (level[*y] == -1) {
                level[*y] = level[x] + 1;
                stack.push_back(make_pair(x, *y));
                DFS(*y, x, stack, level, minLevel, components, criticalVertices, criticalEdges);
                if (minLevel[*y] > level[x])
                    criticalEdges.push_back(make_pair(x, *y));
                if (minLevel[*y] >= level[x]) {
                    criticalVertices.push_back(x);
                    components.push_back(GetComponent(make_pair(x, *y), stack));
                }
            }
        }
        bool usedFather = false;
        for (vector<int>::const_iterator y = edges[x].begin(); y != edges[x].end(); ++y) {
            if (!usedFather && *y == father)
                usedFather = true;
            else
                minLevel[x] = min(minLevel[x], minLevel[*y]);
        }
    }
};

Graph G;
vector< vector<int> > Components;

void Solve() {
    Components = G.GetBiconnectedComponents();
}

void Read() {
    ifstream cin("biconex.in");
    int v, e;
    cin >> v >> e;
    G = Graph(v);
    for (; e > 0; --e) {
        int from, to;
        cin >> from >> to;
        G.AddEdge(--from, --to);
    }
    cin.close();
}

void Print() {
    ofstream cout("biconex.out");
    cout << int(Components.size()) << "\n";
    for (int i = 0; i < int(Components.size()); ++i) {
        for (vector<int>::const_iterator x = Components[i].begin(); x != Components[i].end(); ++x)
            cout << *x + 1 << " ";
        cout << "\n";
    }
    cout.close();
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}