Cod sursa(job #2544680)

Utilizator CandyBucherGaube Robert Gabriel CandyBucher Data 12 februarie 2020 12:52:13
Problema Componente biconexe Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#define NMAX 100010
using namespace std;

ofstream o("biconex.out");

int n,ids[NMAX],low[NMAX],id=0,cbc=0;
bool viz[NMAX],art[NMAX];

stack <pair<int,int> > S;
vector <pair<int,int> > m;
vector <int> v[NMAX],com[NMAX];

void citire(){
    ifstream f("biconex.in");
    int i,m,y,x; f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    f.close();
}
void dfs(int k,int tata){
    ids[k]=low[k]=++id;
    int i,nv;
    for(i=0;i<v[k].size();i++){
        nv=v[k][i];
        if(tata==nv) continue;
        if(!ids[nv]){
            S.push(make_pair(k,nv));
            dfs(nv,k);
            low[k]=min(low[k],low[nv]);
            if(ids[k]<=low[nv]){
                cbc++; int m1,m2;
                do{
                    m1=S.top().first; m2=S.top().second;
                    S.pop();
                    com[cbc].push_back(m1); com[cbc].push_back(m2);
                }while(m1!=k||m2!=nv);
            }
        }
        else low[k]=min(low[k],low[nv]);
    }
}
void articulatie(){
    int i,j;
    for(i=1;i<=n;i++)
    if(!viz[i]){
        dfs(i,0);
    }
    o<<cbc<<'\n';
    for(i=1;i<=cbc;i++)
    {
        for(j=0;j<com[i].size();j++)
            o<<com[i][j]<<" ";
        o<<'\n';
    }
    o.close();
}
int main(){
    citire();
    articulatie();
}