Cod sursa(job #1971123)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 19 aprilie 2017 20:38:52
Problema Componente biconexe Scor 42
Compilator cpp Status done
Runda Arhiva educationala Marime 2.43 kb
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <stack>
#include <bitset>
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 componente;
set<int>comp[MAXN];
int timp;
stack<pair<int, int>>st;
bitset<MAXN> este;
int viz[MAXN];
void citire(){
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    scanf("%d %d", &n, &m);
    int a, b;
    while(m--){
        scanf("%d %d", &a, &b);
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
}
 
void dfs(int nod, int tata){
    ++timp;
    low[nod] = t[nod] = timp;
 
    int copii = 0;
 
    for(auto fiu : graf[nod]){
        if(t[fiu] == -1){
            ++copii;
            st.push(make_pair(nod, fiu));
            dfs(fiu, nod);
 
            low[nod] = min(low[nod], low[fiu]);
 
            if((tata == -1 && copii >= 2) || tata != -1 && low[fiu] >= t[nod]){           
                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(nod);
                comp[componente].insert(fiu);
                st.pop();
                ++componente;
            }
        } else if(fiu != tata) {
            low[nod] = min(low[nod], t[fiu]);
            st.push(make_pair(nod, fiu));
        }
    }
}
 
 
int main(){
    citire();
    memset(t, -1, sizeof(t));
    for(int nod = 1; nod <= n ; ++nod){
        if(t[nod] == -1)
            dfs(nod, -1);
        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;
        }
    }
    printf("%d\n", componente);  
    for(int i = 0; i < componente; i++){
        for(auto it : comp[i]){
            if(!viz[it]){
                viz[it]++;
                printf("%d ", it);
            }
            else if(viz[it] < graf[it].size() - 1 && este[it]){
                printf("%d ", it);
                viz[it]++;
            }
        }
        printf("\n");
    }
}