Cod sursa(job #3256261)

Utilizator AlexandruTigauTigau Alexandru AlexandruTigau Data 13 noiembrie 2024 22:15:03
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector<int> v[100005],aux;
vector<vector<int>> compb;
int y,parent[100005],disc[100005],low[100005],viz[100005];
void tarjan(int x)
{
    viz[x]=1;
    disc[x]=low[x]=++y;
    int children=0;
    aux.push_back(x);
    for(auto i:v[x])
        if(i!=parent[x]){
            if(viz[i])
                low[x]=min(low[x],disc[i]);
            else
            {
                parent[i]=x;
                if(!parent[x])
                    children++;
                tarjan(i);
                low[x]=min(low[x],low[i]);
                if((parent[i]&&low[i]>=disc[x])||(!parent[x]&&children>1))
                {
                    compb.push_back(vector<int>());
                    while(aux.back()!=x)
                    {
                        compb.back().push_back(aux.back());
                        aux.pop_back();
                    }
                    compb.back().push_back(x);
                }
            }}
}
int main()
{
    int n,m;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        f>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
        if(!viz[i])
    {
        tarjan(i);
        if(!aux.empty())
            //compb.push_back(aux);
        aux.clear();
    }
    g<<compb.size();
    for(auto i:compb)
    {
        g<<'\n';
        for(auto j:i)
            g<<j<<" ";
    }
    return 0;
}