Cod sursa(job #2595381)

Utilizator tudorcioc5Cioc Tudor tudorcioc5 Data 7 aprilie 2020 16:59:04
Problema Componente biconexe Scor 48
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.8 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <deque>
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;
deque <pair<int, int>> biconnected_graph;
int nodes, edges, j, k, children_of_1;

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]){
                biconnected_graph.push_back (pair<int, int> (where_to_start, *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];

    }


}


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]){
            biconnected_graph.push_back (pair<int, int> (1, *it));
            dfs_search(*it, 1);
            children_of_1++;
        }
    if (children_of_1 > 1) articulation_points[1] = true;

    int number_of_biconnected = 1;
    for (deque<pair<int, int>>::iterator it = biconnected_graph.begin(); it != biconnected_graph.end(); it++){
        if (articulation_points[it->first] && (level[it -> first] <= minimum_accessible[it -> second]))
            number_of_biconnected++;
    }

    bool reset = true;
    fout.open("biconex.out");
    fout<<number_of_biconnected<<"\n";
    for (; !biconnected_graph.empty(); biconnected_graph.pop_back()){
        if (reset)
            fout<<biconnected_graph.back().second<<" "<<biconnected_graph.back().first<<" ", reset = false;
        
        else fout<<biconnected_graph.back().first<<" ";

        if (articulation_points[biconnected_graph.back().first] && level[biconnected_graph.back().first] <= minimum_accessible[biconnected_graph.back().second])
            fout<<"\n", reset = true;
    }
    fout.close();

    return 0;
}