Cod sursa(job #2595540)

Utilizator tudorcioc5Cioc Tudor tudorcioc5 Data 7 aprilie 2020 21:08:26
Problema Componente biconexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.29 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <deque>
#include <stack>
#include <algorithm>
using namespace std;

ifstream fin;
ofstream fout;

vector <vector<int>> neighbours (100001);
bitset <100001> visited;
vector <int> level (100001);
vector <int> minimum_accessible (100001);
bitset <100001> articulation_points;

vector<vector<int>> biconnected_components;

bool searching_biconnected_component = false;

int nodes, edges, j, k;

void dfs_search(int where_to_start, int parent){
    visited[where_to_start] = true;
    level[where_to_start] = level[parent] + 1;
    minimum_accessible[where_to_start] = level[where_to_start];

    for (vector<int>::iterator it = neighbours[where_to_start].begin(); it != neighbours[where_to_start].end(); it++){
        if (*it != parent){
            if (!visited[*it]){
                dfs_search(*it, where_to_start);
                if (minimum_accessible[*it] < minimum_accessible[where_to_start])
                    minimum_accessible[where_to_start] = minimum_accessible[*it];

                if (level[where_to_start] <= minimum_accessible[*it])
                    articulation_points[where_to_start] = true;     

            }

            else if (level[*it] < minimum_accessible[where_to_start])
                minimum_accessible[where_to_start] = level[*it];
        }
    }


}

void dfs_search_2(int where_to_start, stack <int> &biconnected_stack){
    visited[where_to_start] = true;
    biconnected_stack.push(where_to_start);


    for (vector<int>::iterator it = neighbours[where_to_start].begin(); it != neighbours[where_to_start].end(); it++)
        if(!visited[*it]){
            if ((level[where_to_start] <= minimum_accessible[*it]) && articulation_points[where_to_start]){
                stack<int> biconnected_stack_2;
                biconnected_stack_2.push(where_to_start);
                dfs_search_2(*it, biconnected_stack_2);

            }else dfs_search_2(*it, biconnected_stack);

        }
        vector<int> aux;
        for (; !biconnected_stack.empty(); biconnected_stack.pop())
            aux.push_back(biconnected_stack.top());
        if (aux.size() > 1)
            biconnected_components.push_back(aux);
}


int main (void){
    fin.open ("biconex.in");
    fin>>nodes>>edges;
    for (int i = 1; i<=edges; i++){
        fin>>j>>k;
        neighbours[j].push_back(k);
        neighbours[k].push_back(j);
    }
    fin.close();

    visited[1] = true;
    level[1] = 1;
    minimum_accessible[1] = 1;
    for (vector<int>::iterator it = neighbours[1].begin(); it != neighbours[1].end(); it++)
        if (!visited[*it]){
            dfs_search(*it, 1);
        }

    for (int i=0; i<=nodes; i++)
        visited[i] = false;

    stack<int> biconnected_stack;
    dfs_search_2(1, biconnected_stack);

    for (vector<vector<int>>::iterator it1 = biconnected_components.begin(); it1 != biconnected_components.end(); it1++)
        sort(it1->begin(), it1->end());

    fout.open("biconex.out");
    fout<<biconnected_components.size()<<"\n";
    for (vector<vector<int>>::iterator it1 = biconnected_components.begin(); it1 != biconnected_components.end(); it1++){
        for (vector<int>::iterator it2 = it1->begin(); it2 != it1->end(); it2++)
            fout<<*it2<<" ";
        fout<<"\n";
    }
    fout.close();



    return 0;
}