Cod sursa(job #2123524)

Utilizator catalina200029Olteanu Catalina catalina200029 Data 6 februarie 2018 12:37:42
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.06 kb
#include <bits/stdc++.h>

using namespace std;

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

vector<int> l[100005];
vector<pair<int,int>> st;

int n,m,cod[100005],k,cv[100005],nrcv,viz[100005],low[100005],t[100005],niv[100005],r,nr,sol[100005];

void df(int i) {
    int j;
    viz[i]=1;
    low[i]=niv[i];
    for (j=0;j<l[i].size();j++)
        if (!viz[l[i][j]]) {
            niv[l[i][j]]=niv[i]+1;
            t[l[i][j]]=i;
            df(l[i][j]);
            low[i]=min(low[i],low[l[i][j]]);
            if (low[l[i][j]]>=niv[i])
                nr++;
        }
        else if (l[i][j]!=t[i])
            low[i]=min(low[i],niv[l[i][j]]);
}


void df2(int i) {
    int j,x,y,w,ok1,ok2;
    viz[i]=1;
    low[i]=niv[i];
    for (j=0;j<l[i].size();j++) {
        if (l[i][j]!=t[i] && niv[i]>niv[l[i][j]])
            st.push_back(make_pair(i,l[i][j]));
        if (!viz[l[i][j]]) {
            niv[l[i][j]]=niv[i]+1;
            t[l[i][j]]=i;
            df2(l[i][j]);
            low[i]=min(low[i],low[l[i][j]]);
            if (low[l[i][j]]>=niv[i]) {
                int nr2=0;
                do {
                    x=st[st.size()-1].first;
                    y=st[st.size()-1].second;
                    sol[++nr2]=x;
                    sol[++nr2]=y;
                    st.pop_back();
                } while(!st.empty() && (x!=i || y!=l[i][j]) && (x!=l[i][j] || y!=i));
                sort(sol+1,sol+nr2+1);
                for (w=1;w<=nr2;w++)
                    if (sol[w]!=sol[w-1]) g<<sol[w]<<' ';
                g<<'\n';
            }
        }
        else if (l[i][j]!=t[i])
            low[i]=min(low[i],niv[l[i][j]]);
    }
}

void init() {
    int i;
    for (i=1;i<=n;i++)
        niv[i]=t[i]=low[i]=viz[i]=sol[i]=0;
}

int main() {
    int i,j,x,y;
    f>>n>>m;
    for (i=1;i<=m;i++) {
        f>>x>>y;
        l[x].push_back(y);
        l[y].push_back(x);
    }
    r=1;
    niv[1]=1;
    df(1);
    g<<nr<<'\n';
    init();
    r=1;
    niv[1]=1;
    df2(1);
    return 0;
}