Cod sursa(job #1970963)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 19 aprilie 2017 18:55:31
Problema Componente biconexe Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 2.95 kb
#include <vector>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <stack>
using namespace std;

const int MAXN = 100005;
vector<int>graf[MAXN];
int n, m;
int t[MAXN]; // momentul cand a fost vizitat nodul
int low[MAXN]; // minimul dintre momentul tatalui si momentul nodului
int tata[MAXN]; // tatal din arborele DFS
bool viz[MAXN];
bool este[MAXN]; // Este punct de articulatie?
int componente;
set<int>comp[MAXN];
int timp;
stack<pair<int, int>>st;

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

void citire(){
    in>>n>>m;
    int a, b;
    while(m--){
        in>>a>>b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
}

void dfs(int nod){
    viz[nod] = 1;
    ++timp;
    low[nod] = t[nod] = timp;

    int copii = 0; // numarul de fii din arborele DFS

    for(auto fiu : graf[nod]){
        if(!viz[fiu]){
            ++copii;
            tata[fiu] = nod;
            st.push(make_pair(nod, fiu));
            dfs(fiu);

            low[nod] = min(low[nod], low[fiu]);

            if(tata[nod] == -1 && copii >= 2){
                //Cazul 1: Daca este radacina arborelui DFS si are cel putin 2 fii
                este[nod] = 1;
                while(st.top().first != nod && st.top().second != fiu){
                    comp[componente].insert(st.top().first);
                    comp[componente].insert(st.top().second);
                    st.pop();
                }
                comp[componente].insert(st.top().first);
                comp[componente].insert(st.top().second);
                st.pop();
                ++componente;
            }
            if(tata[nod] != -1 && low[fiu] >= t[nod]){
                //Cazul 2: Daca nu este radacina, insa are cel putin 2 fii independenti
                este[nod] = 1;
                while(st.top().first != nod && st.top().second != fiu){
                    comp[componente].insert(st.top().first);
                    comp[componente].insert(st.top().second);
                    st.pop();
                }
                comp[componente].insert(st.top().first);
                comp[componente].insert(st.top().second);
                st.pop();
                ++componente;

            }
        } else if(fiu != tata[nod]) {
            low[nod] = min(low[nod], t[fiu]);
            st.push(make_pair(nod, fiu));
        }
    }
}


int main(){
    citire();
    memset(tata, -1, sizeof(tata));
    for(int nod = 1; nod <= n ; ++nod){
        if(!viz[nod])
            dfs(nod);
        bool isempty = 1;
        while(!st.empty()){
            isempty = 0;
            comp[componente].insert(st.top().first);
            comp[componente].insert(st.top().second);
            st.pop();
        }
        if(!isempty){
            ++componente;
        }
    }
    out<<componente<<'\n';
    for(int i = 0; i < componente; i++){
        for(auto it = comp[i].begin(); it != comp[i].end(); ++it)
            out<<*it<<' ';
        out<<'\n';
    }
}