Cod sursa(job #2791795)

Utilizator MirunaStefaniaLupascu Miruna-Stefania MirunaStefania Data 31 octombrie 2021 07:45:32
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 16.52 kb
#include <bits/stdc++.h>
#define N 100005


using namespace std;

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

queue<int> q;

int ctComponents = 0;
vector<int> comp[N]; //to print the strongly connected components

class Graph {
private:
    int n, m;

    vector<int> adlist[N];
    bool viz[N] = {0};
    int dist[N] = {0};

    stack<int> s; //final times in dfs

    void dfCritical(int k, int father, int level[], int level_min[], bool visitedCritical[],  vector<vector<int>>& sol); // dfs for critical edges
    void dfBiconnected(int k, int father, int level[N], int level_min[N], vector<vector<int>> &biconnected, pair<int, int> stackk[], int &vf_stack);
    //void dfBiconnected1(int vertex, int father, int level[N], int level_min[N], bool visitedBC[N], vector<set<int>>& biconnected, stack< pair <int, int>>& edges);
    //void component1(int vertex, int node, vector<set<int>> biconnected, stack< pair <int, int>> edges);
public:
    Graph() = default;
    Graph(int n, int m):n(n), m(m){}

    void readDirected();
    void readUndirected();

    void bfs(int first);   //for minimum path
    void dfs(int first);   //for connected components
    void dfsT(int first); //used only for Transpoused --> do not add nodes in s, print the node
                          //we will use "viz" from the transpoused graph
    void printDist();
    void connectedComponents();
    void printGraph();
    Graph transpose();
    void stronglyConnectedComponents();
    void sortTopo(); //dfs and we keep the final times, after a node is finished, we put it in the stack

    bool graphExistsHakimi(vector<int> &dg, int n); //the grades and number of nodes

    void biconnectedComponents();

    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections); /*Input: n = 2, connections = [[0,1]] Output: [[0,1]]*/

};


void Graph::readDirected() {
    for(int i = 1; i <= m; ++i) {
        int x, y;
        fin >> x >> y;
        adlist[x].push_back(y);
    }
}

void Graph::readUndirected() {

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

void Graph::printGraph() {
    for(int i = 1; i <= n; ++i) {
        fout << i <<":";
        for(int j = 0; j < adlist[i].size(); ++j)
            fout << adlist[i][j] << " ";
        fout <<"\n";

    }
}

void Graph::bfs(int first) {
    int node, dim;
    dist[first] = 1;
    viz[first] = 1;
    q.push(first);

    while(!q.empty())
    {
        node = q.front();
        q.pop();
        dim = adlist[node].size();
        for(int i = 0; i < dim; ++i)
            if(!viz[adlist[node][i]])
        {
            fout << adlist[node][i] <<" ";
            viz[adlist[node][i]] = 1;
            dist[adlist[node][i]] = dist[node] + 1;
            q.push(adlist[node][i]);
        }
    }
}

void Graph::dfs(int node){
    int i, dim;
    viz[node] = 1;
    dim = adlist[node].size();
    for(i = 0; i < dim; ++i)
            if(!viz[adlist[node][i]])
                dfs(adlist[node][i]);
    s.push(node);
}

void Graph::dfsT(int node){
    int i, dim;

    comp[ctComponents].push_back(node);//is part of the same component

    viz[node] = 1;
    dim = adlist[node].size();
    for(i = 0; i < dim; ++i)
            if(!viz[adlist[node][i]])
                dfsT(adlist[node][i]);

}

void Graph::printDist(){
    int i;
    for(i = 1; i <= n; ++i)
        fout << dist[i] - 1 << " ";
}

void Graph::connectedComponents() {
    int i, nr = 0;
    for(i = 1; i <= n; ++i)
        if(!viz[i])
    {
        nr++;
        dfs(i);
    }
    fout << nr;

}

Graph Graph::transpose() {
    int i, j;
    Graph gt(n, m);
    for(i = 1; i <= n; ++i)
        for(j = 0; j < adlist[i].size(); ++j)
            gt.adlist[adlist[i][j]].push_back(i);
    return gt;

}

void Graph::stronglyConnectedComponents(){


    int node;
    for(int i = 1; i <= n; ++i)
        if(!viz[i])
            this->dfs(i);
    Graph gt = this->transpose();
    while(!s.empty())
    {
        node = s.top();
        s.pop();
        if(!gt.viz[node])
            {
                ctComponents++;
                gt.dfsT(node);
            }
    }

    int i, j;
    fout << ctComponents << "\n";

    for(i = 1; i <= ctComponents; ++i) {
        for(j = 0; j < comp[i].size(); ++j)
            fout <<comp[i][j] << " ";
        fout << "\n";
            }

}

void Graph::sortTopo(){

    for(int i = 1; i <= n; ++i)
        if(!viz[i])
            dfs(i);
    while(!s.empty())
    {
        fout << s.top() <<" ";
        s.pop();
    }

}

bool Graph::graphExistsHakimi(vector<int> &dg, int n) {
    ///sort the vector of degrees desc
    ///we start with the biggest degree v ant link it with the next v nodes (substract 1 from the next v elements)
    ///repeat until:
    ///1. all the remaining elements are 0 (graph exists)
    ///2. negative values encounter after substraction (doesn't exist)
    ///3. not enough elements remaining after substraction (doesn't exist)

    while(1)
    {
        sort(dg.begin(), dg.end(), greater<>());
        if(dg[0] == 0)
            return true; //all elements equal to 0
        int degree = dg[0];
        dg.erase(dg.begin() + 0);

        if(degree > dg.size())//check if enough elements are in the list
            return false;

        for(int i = 0; i < dg.size(); ++i)
        {
            dg[i]--;
            //check negative
            if(dg[i] < 0)
                return false;
        }
    }
}


void Graph::dfCritical(int k, int father, int level[], int level_min[], bool visitedCritical[],  vector<vector<int>>& sol)
{
    visitedCritical[k] = 1;
    if(father == -1)
         level[k] = 1;
    else
        level[k] = level[father] + 1;
    level_min[k] = level[k];

    int dim = adlist[k].size();
    for (int i = 0; i < dim; ++i)
        if(adlist[k][i] != father)
            {
                int x = adlist[k][i];
                if(visitedCritical[x])    //it's a return edge --> verify if we can reach a higher level
                {
                    if(level_min[k] > level[x])
                        level_min[k] = level[x];

                }
                else
                {
                    dfCritical(x, k,level, level_min, visitedCritical, sol);
                    if(level_min[k] > level_min[x]) // one child has a return edge --> we can reach a higher level
                    {
                        level_min[k] = level_min[x];
                    }


                    ///determine critical connections
                    if(level[k] < level_min[x])
                    {
                        vector<int> current;
                        current.push_back(x);
                        current.push_back(k);
                        sol.push_back(current);
                    }

                }

            }

}


vector<vector<int>> Graph :: criticalConnections(int n, vector<vector<int>>& connections)
{
    int level[N] = {0};
    int level_min[N] = {0};
    bool visitedCritical[N] = {0};

    for(int i = 0; i < connections.size(); ++i)//for each edge
    {
        adlist[connections[i][0]].push_back(connections[i][1]);
        adlist[connections[i][1]].push_back(connections[i][0]);
    }
    vector<vector<int>> sol;//solution of critical edges
    for(int i = 0; i < n; ++i)
        if(!visitedCritical[i])
            dfCritical(i, -1, level, level_min, visitedCritical, sol);
    return sol;

}
/*sol1
void Graph::biconnectedComponents(){
    ///keep adding edges in stack from df tree and when an articulation node is detected
    ///i.e a vertex u has a child v (level_min[v] >= level[u]) --> has no return edge in the subtree
    ///pop all edges from the stack till u-v is found ---> all those edges, including u-v will form a biconnected component

    bool visitedBC[N] = {0};
    int level[N] = {0};
    int level_min[N] = {0};

    vector<set<int>> biconnected; //bcs we want to add nodes based on component's edges
    stack< pair <int, int>> edges; //stack with the edges for df tree

    for(int i = 1; i <= n; ++i)
        if(!visitedBC[i])
            dfBiconnected(i, 0, level, level_min, visitedBC, biconnected, edges);


    set<int, greater<int> >::iterator itr;  //for looping a set
    set<int> s1;
    fout << biconnected.size() << "\n";

    for(int i = 0; i < biconnected.size(); ++i)
    {
        s1 = biconnected[i];
        for (itr = s1.begin(); itr != s1.end(); itr++)
            fout << *itr<<" ";
        fout << "\n";

    }
    for(int i = 1; i <= n; ++i)cout <<level[i] <<" ";
    cout <<"\n";
    for(int i = 1; i <= n; ++i)cout <<level_min[i] <<" ";

}

void Graph::component1(int vertex, int node, vector<set<int>> biconnected, stack< pair <int, int>> edges){

    //cout << vertex << " " << node <<"\n";
    int x, y;
    set<int> comp;  //the current component
    do
    {
        pair <int, int> p = edges.top();
        x = p.first;
        y = p.second;
        cout << x << " " << y <<"\n";

        edges.pop();

        comp.insert(x);
        comp.insert(y);

    }while(x != vertex || y != node);
    cout <<"\n";
    biconnected.push_back(comp);    //add at the biconnected components
}

void Graph::dfBiconnected1(int vertex, int father, int level[N], int level_min[N], bool visitedBC[N], vector<set<int>>& biconnected, stack< pair <int, int>>& edges){



    static int time = 1;
    visitedBC[vertex] = 1;
    level[vertex] = time++;
    level_min[vertex] = level[vertex];
    int dim = adlist[vertex].size();
    for(int i = 0; i < dim ; ++i)
    {
        int node = adlist[vertex][i];
        if(!visitedBC[node])
        {

            edges.push({vertex, node});    //add the edge in the stack

            dfBiconnected(node, vertex, level, level_min, visitedBC, biconnected, edges); //continue the dfs from here

            if(level_min[vertex] > level_min[node] ) //with the current node we can reach a higher level
                level_min[vertex] = level_min[node];

            if(level[vertex] <= level_min[node])   //it's articulation point
                component(vertex, node, biconnected, edges);
        }
        else    //it's a return edge
        {
            if(node != father)
            {
                //it means that is a child that has been already visited (level[vertex] < level[node])
                //compare level_min[vertex], level[node] to see if using this node  we can go to a higer level
                if(level_min[vertex] > level[node])
                    level_min[vertex] = level[node];
            }

        }
    }


}
*/

/*sol2
void Graph::biconnectedComponents(){
    ///keep adding nodes in the stack until we finish the biconnected component
    int level[N] = {0};
    int level_min[N] = {0};
    bool visitedBC[N] = {0};
    vector<set<int>> biconnected;//vector with the components
    stack<int> elem;// the vertex visited in dfs
    for(int i = 1; i <= n; ++i)
        if(!visitedBC[i])
        dfBiconnected(i, 0, level, level_min, visitedBC,biconnected,elem);
    fout << biconnected.size() <<"\n";

    set<int, greater<int> >::iterator itr;  //for looping a set
    for(int i = 0; i < biconnected.size(); i++)
    {
        set<int> s1 = biconnected[i];
         for (itr = s1.begin(); itr != s1.end(); itr++)
            fout << *itr<<" ";
        fout <<"\n";
    }
}

void Graph::dfBiconnected(int k, int father, int level[N], int level_min[N], bool visitedBC[N], vector<set<int>> &biconnected, stack<int> &elem){
    visitedBC[k] = 1;
    elem.push(k);

    level[k] = level[father] + 1;
    level_min[k] = level[k];

    int dim = adlist[k].size();
    for (int i = 0; i < dim; ++i)
        if(adlist[k][i] != father)
            {
                int x = adlist[k][i];
                if(visitedBC[x])    //it's a return edge --> verify if we can reach a higher level
                {
                    if(level_min[k] > level[x])
                        level_min[k] = level[x];

                }
                else
                {
                    dfBiconnected(x, k,level, level_min, visitedBC, biconnected, elem);
                    if(level_min[k] > level_min[x]) // one child has a return edge --> we can reach a higher level
                    {
                        level_min[k] = level_min[x];
                    }


                    ///determine a biconnected component
                    if(level[k] <= level_min[x])    //the conditon to be able to go back at the articulation point
                    {
                        set<int> current;
                        while(elem.top() != k)
                        {

                            current.insert(elem.top());
                            elem.pop();
                        }
                        current.insert(k);

                        current.insert(x);
                        biconnected.push_back(current);
                    }
                }

            }


}
*/
void Graph::biconnectedComponents(){
    ///keep adding nodes in the stack until we finish the biconnected component
    int level[N] = {0};
    int level_min[N] = {0};

    vector<vector<int>> biconnected;//vector with the components
    pair<int, int> stackk[N * 2];// a vector  with the nodes visited in dfs(added by their edges)
    int vf_stack = 0;


    dfBiconnected(1, 0, level, level_min, biconnected, stackk, vf_stack);

    fout << biconnected.size() << "\n";

    for(int i = 0; i < biconnected.size(); ++i)
    {
        vector <int> comp = biconnected[i];
        for(int j = 0 ; j < comp.size(); ++j)
            fout << comp[j] <<" ";
        fout <<"\n";
    }


}

void Graph::dfBiconnected(int k, int father, int level[N], int level_min[N], vector<vector<int>> &biconnected, pair<int, int> stackk[], int &vf_stack){
    level[k] = level[father] + 1;
    level_min[k] = level[k];

    int dim = adlist[k].size();
    for (int i = 0; i < dim; ++i)
    {
        int node = adlist[k][i];
        if(level[node])//if visited
        {
            if(node != father && level[node] < level_min[k])   //return edge
                level_min[k] = level[node];
        }
        else
        {
           stackk[++vf_stack] = {k, node};
            dfBiconnected(node, k, level, level_min, biconnected, stackk, vf_stack);

            if(level_min[k] > level_min[node])//one of the childs has a return edge
                level_min[k] = level_min[node];

            if(level_min[node] >= level[k])
            {
                biconnected.push_back({});  //create e new biconnected component
                while(stackk[vf_stack].first != k)
                    biconnected.back().push_back(stackk[vf_stack--].second);    //add at the last component the nodes
                biconnected.back().push_back(stackk[vf_stack].second);
                biconnected.back().push_back(stackk[vf_stack].first);   //add for the last edge both nodes, the articulation point is part of more components
                vf_stack--;
            }
        }
    }



}
int main()
{
    int i, first, n, m;
    vector<int> dg;
/*
    fin >> n >> m;
    Graph g(n, m);
*/

    /*
    g.readOriented();
    g.bfs(first);
    g.printDist();
*/
/*
    g.readUndirected();
    g.connectedComponents();
*/

 ///ctc ///time limit exceeded pe un test
    /*g.readDirected();
    g.stronglyConnectedComponents();
*/

///sortare topologica
/*
    g.readDirected();
    g.sortTopo();
    */

    ///HAVEL-HAKIMI
    /*
    fin >> n;
    Graph g(n, 0);
    for(int i = 1; i <= n; ++i)
    {
        fin >> first;
        dg.push_back(first);
    }
    if(g.graphExistsHakimi(dg, n))
        fout << "yes";
    else fout << "no";
*/

///!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!critical connection--> afiseaza bine
/*
    //fin >> n;
    n = 2;
    Graph g(n, 0);
    vector<vector<int>>connections = {{0,1}};
    vector<vector<int>> sol = g.criticalConnections(n, connections);
    fout << sol.size() << "\n";
    for(int i = 0; i < sol.size(); ++i)
    {
        for(int j = 0; j < sol[i].size(); ++j)
            fout << sol[i][j] << " ";
        fout <<"\n";
    }
*/
///componente biconexe

    fin >> n >> m;
    Graph g(n, m);
    g.readUndirected();
    g.biconnectedComponents();




    return 0;
}