Cod sursa(job #2793743)

Utilizator MateiDorian123Nastase Matei MateiDorian123 Data 3 noiembrie 2021 22:37:44
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 15.81 kb
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <fstream>
#include <list>
#include <algorithm>
#include <set>
using namespace std;

ofstream fout("biconex.out");

class Graph{

protected:
    int n, m; /// n -> number of nodes / m -> number of edges
    vector<vector<int> > l; /// list of adjacency

public:
    Graph(int n = 1, int m = 0);
    Graph(const Graph &g);

    Graph& operator= (const Graph &g);


    int get_numEdges();
    int get_numNodes();

    friend istream& operator>>(istream& in, Graph& obj);
    friend ostream& operator<<(ostream& out, const Graph& obj);

    virtual ostream& print(ostream& out) const;
    virtual istream& read(istream& in);
    virtual void read_from_file(string filename) = 0;

    void dfs(int start);

    void do_dfs(int start, vector<bool> &viz, bool print);
    int num_of_components();

    void bfs(int start);
    void do_bfs(int start, vector<int> &dist, bool print);
    void dist_from_node(int start);

    virtual ~Graph() = 0;
};


///constructors
Graph :: Graph (int n, int m) : l(n + 1){
    /// the default case is to construct a graph
    /// with one node and 0 edges

    this->n = n;
    this->m = m;

}

Graph :: Graph (const Graph &g) : l(g.n) {
    /// copy constructor

    this->n = g.n;
    this->m = g.m;

    for(int i = 0; i < g.n; ++i)
        l.push_back(g.l[i]);
}


/// getters
int Graph :: get_numEdges() {
    return m;
}

int Graph :: get_numNodes() {
    return n;
}


/// operators
Graph& Graph :: operator= (const Graph &g){
     if(this != &g){
        this->n = g.n;
        this->m = g.m;

        if(!this->l.empty())
            l.clear();

        for(int i = 0; i <= g.n; ++i)
            l.push_back(g.l[i]);
     }

     return *this;
}

istream& operator>>(istream& in, Graph& g){
    g.read(in);
    return in;
}

ostream& operator<<(ostream& out, Graph& g){
    g.print(out);
    return out;
}


/// destructor
Graph :: ~Graph(){
    if(!this->l.empty())
        l.clear();
}


/// methods
istream& Graph :: read(istream& in){
    /// the default format is n m (same line) followed
    /// by m pairs x y, each on one line, representing
    /// the edges

    cin >> n >> m;
    return in;
}

ostream& Graph :: print(ostream& out) const{
    /// the default format is n m on one line followed
    /// by the number of the current node and a list of every
    /// reachable nodes

    cout << n << " " << m << "\n";

    for(int i = 1; i <= n; ++i){
        cout << i << ": ";
            for(unsigned int j = 0; j < l[i].size() ; ++j)
                cout << l[i][j] << " ";
        cout << "\n";
    }

    return out;
}

void Graph :: do_dfs(int start, vector<bool> &viz, bool print){
    /// do DFS from start node
    /// if print is true -> print the node as
    /// you visit them

    if(print)
        fout << start << " ";

    viz[start] = 1;

    for(auto it = l[start].begin(); it != l[start].end(); ++it)
        if(!viz[*it])
            do_dfs(*it, viz, print);

}

void Graph::dfs(int start){
    /// this function initializes the vector viz
    /// used to mark visited node and calls DFS
    /// this function prints the DFS traversal
    /// of the graph with the start node - start

    vector<bool> viz(n + 1, 0);
    do_dfs(start, viz, 1);
}

int Graph :: num_of_components(){
    /// this function returns the number
    /// of connected components of the graph

    int ct = 0; /// variable to count the components
    vector<bool> viz(n + 1, 0);

    for(int i = 1; i <= n; ++i){
        if(!viz[i]){
            ct++;
            do_dfs(i, viz, 0);
        }
    }

    return ct;
}

void Graph :: do_bfs(int start, vector<int>& dist, bool print = 0){
    /// do BFS from start node
    /// mark in dist[i] the minimum distance
    /// between i and start

    queue<int> q;
    vector<bool> viz(n + 1, 0);

    /// initialization
    viz[start] = 1;
    q.push(start);
    dist[start] = 1;

    /// BFS
    while(!q.empty()){
        int k = q.front();

        if(print)
            cout<< k << " ";

        for(auto i: l[k])
            if(viz[i] == 0){
                viz[i] = 1;
                dist[i] = dist[k] + 1;
                q.push(i);
           }
        q.pop();
    }
}

void Graph :: bfs(int start){
    /// this function initializes the vector dist
    /// and calls BFS
    /// this function prints the BFS traversal
    /// of the graph with the start node - start

    vector<int> dist(n + 1, 0);
    do_bfs(start, dist, 1);
}

void Graph :: dist_from_node (int start){
    /// this function calculates the distance between
    /// the start node and every other node in the graph
    /// if the node is unreachable -> the distance is -1

    vector<int>dist(n + 1, 0);
    do_bfs(start, dist);

    for(int i = 1; i <= n; i ++)
        fout << dist[i] - 1<<" ";
}

//----------------------------------------------------------------------

class UnorientedGraph : public Graph{

public:
    UnorientedGraph(int n = 1, int m = 0) : Graph(n, m) {};
    UnorientedGraph(int n, int m, vector<pair<int, int> > v);
    UnorientedGraph& operator+=(const pair<int, int> edge);
    istream& read(istream& in) override;
    void read_from_file(string filename);
    void do_dfs_with_bridges(int start, int &time, vector<bool> &viz, vector<int> &disc, vector<int> &low, vector<int> &parent);
    void print_bridges();
    void do_biconex(int son, int dad, vector<bool> &viz, vector<int> &disc, vector<int> &low, stack<int> &s, string &response, int &ct);
    void biconex();
    bool havel_hakimi(vector<int> d);
};


/// Constructor
UnorientedGraph :: UnorientedGraph(int n, int m, vector<pair<int, int> > v) : Graph(n, m){
    for(auto it : v){
        l[it.first].push_back(it.second);
        l[it.second].push_back(it.first);
    }
}


/// read method
istream& UnorientedGraph :: read(istream& in){
    Graph::read(in); /// call read from base
    UnorientedGraph temp(n, m);

    for(int i = 1; i <= m; i ++){
        int x, y;
        cin >> x >> y;
        temp.l[x].push_back(y);
        temp.l[y].push_back(x);
    }

    operator=(temp);
    return in;
}

void UnorientedGraph :: read_from_file(string filename){
    int n, m;

    ifstream input;
    input.open(filename);

    input >> n >> m;

    UnorientedGraph g(n, m);
    for(int i = 1; i <= m; i ++){
        int x, y;
        input >> x >> y;
        g += make_pair(x, y);
    }
    *this = g;
    input.close();

}

/// Operators
UnorientedGraph& UnorientedGraph :: operator+=(const pair<int, int> edge){
    /// add edge to graph
    m++;
    l[edge.first].push_back(edge.second);
    l[edge.second].push_back(edge.first);
    return *this;
}

void UnorientedGraph :: do_dfs_with_bridges(int start, int &time, vector<bool> &viz, vector<int> &disc, vector<int> &low, vector<int> &parent){

    viz[start] = 1;
    disc[start] = low[start] = ++time;

    for(auto node : l[start]){
        if(!viz[node]){
            parent[node] = start;
            do_dfs_with_bridges(node, time, viz, disc, low, parent);

            low[start] = min(low[start], low[node]);
            if (low[node] > disc[start])
                cout << start <<" " << node << endl;
        }
        else if(node != parent[start])
            low[start]  = min(low[start], disc[node]);
    }

}

void UnorientedGraph :: print_bridges(){

    vector<bool> viz(n + 1, 0);
    vector<int> disc(n + 1);
    vector<int> low(n + 1);
    vector<int> parent(n + 1, -1);
    int time = 0;

    for(int i = 1; i <= n; i++)
        if (!viz[i])
            do_dfs_with_bridges(i, time, viz, disc, low, parent);
}

bool UnorientedGraph :: havel_hakimi(vector<int> v){
    ///this method receives a vector of integers
    /// as parameters and returns true if there is a graph
    /// with the given integers as degrees or false otherwise
    /// if it returns true, *this will be the graph formed

    int n_nodes = v.size(), s = 0;
    UnorientedGraph temp(n_nodes);
    vector<pair<int, int> > d(n_nodes); /// d[i].first = v[i], d[i].scond = number of node

    for(auto elem : v){
        if(elem > n_nodes) return 0;
        s += elem;
    }

    if(s % 2 == 1) return 0;

    for(int i = 1; i <= n_nodes; ++i)
        d[i - 1] = make_pair(v[i - 1], i);
    /*for(int i = 0; i< n_nodes; i++)
            cout<<d[i].first<<" "<<d[i].second<<"\n";*/


    while(true){
        sort(d.begin(), d.end(), [](pair<int, int> a, pair<int, int> b) { return a.first > b.first;});

        if(d[0].first == 0) {*this = temp; return 1;}

        for(int i = 1; i < n_nodes && d[0].first; ++i){
            d[0].first--;
            d[i].first--;
            if(d[i].first < 0) return 0;
            temp += make_pair(d[0].second, d[i].second);
        }
    }

}

/*void UnorientedGraph :: do_biconex(int start, vector<bool> &viz, vector<int> &disc, vector<int> &low, stack<int> &s, string &response, int &ct){

    viz[start] = 1;
    s.push(start);
    low[start] = disc[start];

    for(auto node : l[start])
        if(!viz[node]){
            disc[node] = disc[start] + 1;
            do_biconex(node, viz, disc, low, s, response, ct);

            low[start] = min(low[start], low[node]);

            if(low[node] >= disc[start]){
                set<int> temp;
                while(s.top() != node){
                    temp.insert(s.top());
                    s.pop();
                }
                temp.insert(node);
                temp.insert(start);
                s.pop();
                ct ++;
                for(auto elem : temp)
                    response += (to_string(elem) + " ");
                response += "\n";
                //components.push_back(temp);
            }
        }
            else /// back-edge
                if(disc[node] < disc[start] - 1)
                    low[start] = min(low[start], disc[node]);



}*/

void UnorientedGraph :: do_biconex(int son, int dad, vector<bool> &viz, vector<int> &disc, vector<int> &low, stack<int> &s, string &response, int &ct){

    viz[son] = 1;
    disc[son] = disc[dad] + 1;
    low[son] = disc[son];

    for(auto node : l[son])
        if(node != dad){
            if(!viz[node]){ ///back-edge
                s.push(node);
                do_biconex(node, son, viz, disc, low, s, response, ct);

                low[son] = min(low[son], low[node]);

                if(disc[son] <= low[node]){
                    ct++;
                    s.push(son);

                    while(!s.empty() && s.top() != node){
                        response += (to_string(s.top()) + " ");
                        s.pop();
                    }
                    if(!s.empty()){
                        response += (to_string(s.top()) + " ");
                        s.pop();
                    }
                    response += "\n";
                }
            }
            else
                if(disc[node] < low[son])
                    low[son] = disc[node];
        }
}


void UnorientedGraph :: biconex(){
    //vector<set<int> > components;
    stack<int> s;
    vector<int> disc(n + 1, -1);
    vector<int> low(n + 1, -1);
    vector<bool> viz(n + 1, 0);
    string response = "";
    int ct = 0;

    disc[1] = 1;
    do_biconex(2, 1, viz, disc, low, s, response, ct);

    /*fout<<components.size()<<"\n";
    for(auto component : components){
        for(auto node : component)
            fout<<node<<" ";
        fout<<"\n";
    }*/

    fout<<ct<<"\n";
    fout<<response;
}

//----------------------------------------------------------------------

class OrientedGraph : public Graph{

public:
    OrientedGraph(int n = 1, int m = 0) : Graph(n, m) {};
    OrientedGraph(int n, int m, vector<pair<int, int> > v);
    OrientedGraph& operator+=(const pair<int, int> edge);
    istream& read(istream& in) override;
    void topological_sort();
    inline void do_dfs(int start, vector<bool> &viz, stack<int> &S);
    void read_from_file(string filename);
    OrientedGraph transpose_graph() const;
    void ctc();

};

/// Constructor
OrientedGraph :: OrientedGraph(int n, int m, vector<pair<int, int> > v) : Graph(n, m){
    for(auto it : v)
        l[it.first].push_back(it.second);
}


/// read method
istream& OrientedGraph :: read(istream& in){
    Graph::read(in); /// call read from base
    OrientedGraph temp(n, m);

    for(int i = 1; i <= m; i ++){
        int x, y;
        cin >> x >> y;
        temp.l[x].push_back(y);
    }

    operator=(temp);
    return in;
}

void OrientedGraph :: read_from_file(string filename){
    int n, m;

    ifstream input;
    input.open(filename);

    input >> n >> m;

    OrientedGraph g(n, m);
    for(int i = 1; i <= m; i ++){
        int x, y;
        input >> x >> y;
        g += make_pair(x, y);
    }
    *this = g;
    input.close();

}

/// Operators
OrientedGraph& OrientedGraph :: operator+=(const pair<int, int> edge){
    /// add edge to graph
    m++;
    l[edge.first].push_back(edge.second);
    return *this;
}

/// methods
void OrientedGraph :: do_dfs(int start, vector<bool> &viz, stack<int> &S){
    viz[start] = 1;
    for(auto node : l[start])
        if(!viz[node])
            do_dfs(node, viz, S);

    S.push(start);
}

void OrientedGraph :: topological_sort(){

    vector<bool> viz(n + 1, 0);
    stack<int> S;

    for(int i = 1; i <= n; ++ i)
        if(!viz[i]) do_dfs(i, viz, S);

    while(!S.empty()){
        fout << S.top() << " "; /// de schimbat in cout cand pun pe github
        S.pop();
    }
}

OrientedGraph OrientedGraph :: transpose_graph() const {

    OrientedGraph gt(this->n, this->m);

    for(int i = 1; i <= n; i ++)
        for(auto node : l[i])
            gt += make_pair(node, i);

    return gt;
}

void OrientedGraph :: ctc(){

    OrientedGraph gt = transpose_graph();
    vector<bool> viz(n + 1, 0);
    stack<int> S;
    int ct = 0;
    int current_node;
    string response = "";

    for(int i = 1; i <= n; ++ i)
        if(!viz[i]) do_dfs(i, viz, S);

    fill(viz.begin(), viz.end(), 0); /// reinitialize viz

    while(!S.empty()){
        current_node = S.top();
        S.pop();
        if(!viz[current_node]){
            stack<int> component;

            ct ++;
            gt.do_dfs(current_node, viz, component);

            while(!component.empty()){
                response += (to_string(component.top()) + " ");
                component.pop();
            }
            response += "\n";
        }
    }

    fout<<ct<<"\n";
    fout<<response;

}
//----------------------------------------------------------------------


/*void Solve(){
    int n, m, start;

    fin >> n >> m >> start;

    OrientedGraph g(n, m);

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

    g.dist_from_node(start);
} BFS infoarena 100 pcte */

/*void Solve(){
    int n, m;
    UnorientedGraph g;
    g.read_from_file("bfs.in");

    fout << g.num_of_components();
}*/

/*void Solve(){
    int n, m;

    fin >> n >> m;

    OrientedGraph g(n, m);
    for(int i = 1; i <= m; i ++){
        int x, y;
        fin >> x >> y;
        g += make_pair(x, y);
    }

    g.topological_sort();
}*/

int main()
{
    /*int n;
    vector<int> d;

    cin>>n;
    for(int i = 1; i <= n; i ++){
        int x;
        cin>>x;
        d.push_back(x);
    }

    UnorientedGraph g;
    bool r = g.havel_hakimi(d);
    cout<<r<<"\n";
    if(r)
        cout<<g;
*/
    UnorientedGraph g;
    g.read_from_file("biconex.in");
    g.biconex();
    return 0;
}