Cod sursa(job #2801694)

Utilizator As932Stanciu Andreea As932 Data 16 noiembrie 2021 19:32:45
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 1e5 + 5;

int n, m;
vector <int> adj[nmax], disc_time, lowest_anc;
stack < pair<int,int> > st;
vector <vector<int> > comp;

void read(){
    fin >> n >> m;

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

    disc_time.assign(n + 1, -1);
    lowest_anc.resize(n + 1);
}

void biconnected_comp(int parent, int node){
    vector <int> c;
    int x, y;

    do {
        x = st.top().first, y = st.top().second;
        st.pop();
        c.push_back(x);
        c.push_back(y);
    } while(x != parent || y != node);

    comp.push_back(c);
}

void dfs(int node, int parent, int discTime){
    disc_time[node] = lowest_anc[node] = discTime;

    for(vector <int>::iterator it = adj[node].begin(); it != adj[node].end(); it++){
        if(*it == parent)
            continue;
        if(disc_time[*it] == -1){
            st.push({node, *it});
            dfs(*it, node, discTime + 1);
            lowest_anc[node] = min(lowest_anc[node], lowest_anc[*it]);
            if(lowest_anc[*it] >= disc_time[node])
                biconnected_comp(node, *it);
        } else
            lowest_anc[node] = min(lowest_anc[node], disc_time[*it]);
    }
}

void print_ans(){
    fout << comp.size() << "\n";

    for(int i = 0; i < comp.size(); i++){
        sort(comp[i].begin(), comp[i].end());
        comp[i].erase(unique(comp[i].begin(), comp[i].end()), comp[i].end());
        for(int j = 0; j < comp[i].size(); j++)
            fout << comp[i][j] << " ";
        fout << "\n";
    }
}

int main()
{
    read();
    dfs(1, 0, 0);
    print_ans();

    return 0;
}