Cod sursa(job #1690273)

Utilizator tudormaximTudor Maxim tudormaxim Data 14 aprilie 2016 22:14:02
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
#include <algorithm>
using namespace std;

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

const int nmax = 1e5+5;
vector <int> g[nmax], comp[nmax];
bitset <nmax> viz;
stack <pair<int,int> > st;
int low[nmax], lev[nmax], nr;

void get_comp(int x, int y) {
    int a, b;
    nr++;
    do {
        a=st.top().first;
        b=st.top().second;
        comp[nr].push_back(b);
        st.pop();
    } while(a!=x || b!=y);
    comp[nr].push_back(a);
}

void dfs(int dad) {
    viz[dad]=true;
    low[dad]=lev[dad];
    for(auto son : g[dad]) {
        if(viz[son]==false) {
            lev[son]=lev[dad]+1;
            st.push({dad, son});
            dfs(son);
            low[dad]=min(low[dad], low[son]);
            if(low[son] >= lev[dad])  ///nodul 'dad' este critic
                get_comp(dad, son);
        }
        else low[dad]=min(low[dad], lev[son]);
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    int i, x, y, n, m;
    fin >> n >> m;
    for(i=1; i<=m; i++) {
        fin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    lev[1]=1;
    dfs(1);
    fout << nr << '\n';
    for(i=1; i<=nr; i++) {
        sort(comp[i].begin(), comp[i].end());
        for(auto it : comp[i])
            fout << it << " ";
        fout << "\n";
    }
    return 0;
}