Cod sursa(job #2697119)

Utilizator QubeeStefan Ste Qubee Data 17 ianuarie 2021 18:17:25
Problema Componente biconexe Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
using namespace std;

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

int n,m,j,x,y,nr=0,niv,viz[100009],low[100009];
vector <int> G[100009],c[100009];
bool s[100009];
stack <int> st;

void dfs(int nod){

    viz[nod]=low[nod]=++niv;
    s[nod]=1;
    st.push(nod);

    for(unsigned int i=0;i<G[nod].size();i++){
        int nou=G[nod][i];

        if(!viz[nou]){
            dfs(nou);
            low[nod]=min(low[nod],low[nou]);

            if(viz[nod]<=low[nou]){
                nr++;
                int x=st.top();
                st.pop();

                while(x!=nou){
                    s[x]=0;
                    c[nr].push_back(x);
                    x=st.top();
                    st.pop();
                }

                s[nou]=0;
                c[nr].push_back(nou);
                c[nr].push_back(nod);
            }
        }
        else if(s[nou])
            low[nod]=min(low[nod],viz[nou]);
    }
}

int main(){

    f>>n>>m;

    for(int i=0;i<m;i++){
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    for(int i=0;i<n;i++)
        if(!viz[i])
            dfs(i);

    g<<nr<<endl;

    for(int i=0;i<nr;i++){
        for(unsigned int j=0;j<c[i].size();j++)
            g<<c[i][j]<<' ';
        g<<endl;
    }
    return 0;
}