Cod sursa(job #2499994)

Utilizator victorzarzuZarzu Victor victorzarzu Data 27 noiembrie 2019 08:53:48
Problema Componente biconexe Scor 62
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,nr,num,start = 1;
int dfn[100001],low[100001];
vector<vector<int>> a(100001,vector<int>());
vector<vector<int>> componente(100001,vector<int>());
struct Muchie{
    int f;
    int t;
};
stack<Muchie> S;
void Citire()
{
    f>>n>>m;
    int x,y;
    for(int i=1;i<=m;++i)
    {
        f>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
}

void Initializare()
{
    for(int i=1;i<=n;++i) dfn[i] = low[i] = -1;
    S.push({start,-1});
}


void Pastrare(int x,int u)
{
    ++nr;
    Muchie p;
    do{
        p = S.top();
        if(find(componente[nr].begin(),componente[nr].end(),p.f) == componente[nr].end()) componente[nr].push_back(p.f);
        if(find(componente[nr].begin(),componente[nr].end(),p.t) == componente[nr].end()) componente[nr].push_back(p.t);
        S.pop();
    }while(p.f != x && p.t != u);
}

void Biconex(int u, int tu)
{
    dfn[u] = low[u] = ++num;
    for(vector<int>::iterator it=a[u].begin();it!=a[u].end();++it)
    {
        if(*it != tu && dfn[*it] < dfn[u]) S.push({*it,u});
        if(dfn[*it] == -1)
        {
            Biconex(*it,u);
            low[u] = min(low[*it],low[u]);
            if(low[*it] >= dfn[u])
                Pastrare(*it,u);
        }
        else
        {
            if(*it != tu)
                low[u] = min(low[u],dfn[*it]);
        }
    }
}

int main()
{
    Citire();
    Initializare();
    Biconex(start,-1);
    g<<nr<<'\n';
    for(int i=1;i<=nr;++i)
    {
        for(vector<int>::iterator it=componente[i].begin();it!=componente[i].end();++it)
            g<<*it<<" ";
        g<<'\n';
    }
    return 0;
}