Cod sursa(job #2544694)

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

ofstream o("biconex.out");

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

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(nv==tata) continue;
        if(ids[nv]==0){
            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(ids[i]==0) dfs(i,0);
    o<<cbc<<'\n';
    for(i=1;i<=cbc;i++)
    {
        sort(com[i].begin(), com[i].end());
        com[i].erase(unique(com[i].begin(), com[i].end()), com[i].end());
        for(j=0;j<com[i].size();j++)
            o<<com[i][j]<<" ";
        o<<'\n';
    }
    o.close();
}
int main(){
    citire();
    articulatie();
}