Cod sursa(job #2115331)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 26 ianuarie 2018 17:23:35
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <fstream>
#include <vector>
#define Bmax 100002
#define Nmax 100002
#define pii pair<int,int>
using namespace std;

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

int n,m,N[Nmax],p;
char buffer[Bmax];
bool uz[Nmax];
vector<int> v[Nmax],res2;
vector<int> st;
vector<vector<int> > res;

bool digit(int x) {if (x>='0' && x<='9') return 1;return 0;}

void read(int &x){
    x = 0;
    while (!digit(buffer[p])){
        p++;
        if (p==Bmax) f.read(buffer,Bmax), p = 0;
    }
    while (digit(buffer[p])){
        x = x*10+buffer[p]-'0';
        p++;
        if (p==Bmax) f.read(buffer,Bmax),p = 0;
    }
}

int dfs(int nod,int niv,int ant){
    int mn = niv,k = st.size()+1;
    uz[nod] = 1;
    N[nod] = niv;
    st.push_back(nod);
    for (auto it : v[nod]){
        if (it==ant) continue;
        if (uz[it]){
            mn = min(mn,N[it]);
            continue;
        }
        int x = dfs(it,niv+1,nod);
        mn = min(mn,x);

    }

    if (mn>=niv-1 && nod!=1){
        while (st.size()>=k){
            res2.push_back(st.back());
            st.pop_back();
        }
        res2.push_back(ant);
        res.push_back(res2);
        res2.clear();
    }

    return mn;
}

int main()
{
    f.read(buffer,Bmax);

    read(n);read(m);
    for (int i=1;i<=m;i++){
        int x,y;
        read(x);read(y);
        v[x].push_back(y);
        v[y].push_back(x);
    }

    for (int i=1;i<=n;i++)
        if (!uz[i]) dfs(i,1,-1);

    g<<res.size()<<'\n';
    for (auto it : res){
        for (auto it2 : it)
            g<<it2<<' ';
        g<<'\n';
    }

    return 0;
}