Cod sursa(job #2323575)

Utilizator TudorFinaruTudor Cristian Finaru TudorFinaru Data 19 ianuarie 2019 13:11:00
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.08 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,m,nma[100003],nivel[100003],nrcomp;
bool viz[100003];

set<pair<int, int> >punti;
set<int>critice;
vector<int>v[100003];
stack<int>s;
vector<int>comp[100003];

void dfs(int k, int tata)
{
    s.push(k);
    int x;
    vector<int>::iterator it;
    viz[k]=1;
    nivel[k]=nivel[tata]+1;
    nma[k]=nivel[k];
    for(it=v[k].begin();it!=v[k].end();++it)
    {
        x=*it;
        if(x!=tata)
        {
            if(viz[x]){
                if(nma[k]>nivel[x]) nma[k]=nivel[x];
            }
            else{
                dfs(x,k);
                if(nma[k]>nma[x]) nma[k]=nma[x];/*
                ///pcte de articulatie
                if(nivel[k]<=nma[x] && k!=1) critice.insert(k);
                ///punti
                if(nivel[k]<nma[x]) punti.insert(make_pair(k,x));*/
                ///comp biconexe
                if(nivel[k]<=nma[x])
                {
                    nrcomp++;
                    while(s.top()!=x){
                        comp[nrcomp].push_back(s.top());
                        s.pop();
                    }
                    comp[nrcomp].push_back(x);
                    s.pop();
                    comp[nrcomp].push_back(k);
                }
            }
        }
    }
}

int main()
{
    int i,x,y;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    ///=================/
    /*
    set<int>::iterator it;
    for(it=critice.begin();it!=critice.end();++it) g<<*it<<' ';
    g<<'\n';
    ///=================
    set<pair<int, int> >::iterator it1;
    for(it1=punti.begin();it1!=punti.end();++it1) g<<it1->first<<' '<<it1->second<<'\n';*/
    ///=================
    g<<nrcomp<<'\n';
    vector<int>::iterator it2;
    for(i=1;i<=nrcomp;i++)
    {
        for(it2=comp[i].begin();it2!=comp[i].end();++it2) g<<*it2<<' ';
        g<<'\n';
    }

    f.close();
    g.close();
    return 0;
}