Cod sursa(job #2123504)

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

using namespace std;

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

vector<int> l[100005],sol[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;

void df(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;
            df(l[i][j]);
            low[i]=min(low[i],low[l[i][j]]);
            if (low[l[i][j]]>=niv[i]) {
                nr++;
                do {
                    ok1=ok2=0;
                    x=st[st.size()-1].first;
                    y=st[st.size()-1].second;
                    for (w=0;w<sol[nr].size();w++)
                        if (sol[nr][w]==x) ok1=1;
                        else if (sol[nr][w]==y) ok2=1;
                    if (!ok1) sol[nr].push_back(x);
                    if (!ok2) sol[nr].push_back(y);
                    st.pop_back();
                } while((x!=i || y!=l[i][j]) && (x!=l[i][j] || y!=i));
            }
        }
        else if (l[i][j]!=t[i])
            low[i]=min(low[i],niv[l[i][j]]);
    }
}

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';
    for (i=1;i<=nr;i++) {
        sort(sol[i].begin(),sol[i].end());
        for (j=0;j<sol[i].size();j++)
            g<<sol[i][j]<<' ';
        g<<'\n';
    }
    return 0;
}