Cod sursa(job #3004474)

Utilizator AndreiBOTOBotocan Andrei AndreiBOTO Data 16 martie 2023 12:48:38
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.25 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

ifstream fin ("biconex.in");
ofstream fout ("biconex.out");

const int NMAX=1e5+5;

stack<int>stiva;

vector<int>v[NMAX];
vector<int>cbc[NMAX];
vector<pair<int,int>>punti;

bool art[NMAX];
int ti[NMAX];
int tm[NMAX];
int total;
int kon;

void dfs(int p,int tata)
{
    int fii=0;
    ti[p]=++kon;
    tm[p]=ti[p];
    stiva.push(p);
    for(auto i:v[p])
    {
        if(tata!=i)
        {
            if(!ti[i])
            {
                dfs(i,p);
                tm[p]=min(tm[p],tm[i]);
                if(tm[i]>=ti[p])
                {
                    total++;
                    while(stiva.top()!=i)
                    {
                        cbc[total].push_back(stiva.top());
                        stiva.pop();
                    }
                    cbc[total].push_back(i);
                    stiva.pop();
                    cbc[total].push_back(p);
                    if(tata!=0)
                        art[p]=true;
                }
                if(tm[i]>ti[p])
                    punti.push_back(make_pair(p,i));
                fii++;
            }
            else
                tm[p]=min(tm[p],ti[i]);
        }
    }
    if(tata==0 && fii>1)
        art[p]=true;
}

int main()
{
    int cer,n,m,i,j,x,y;
    cer=1;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(i=1;i<=n;i++)
    {
        if(!ti[i])
            dfs(i,0);
    }
    if(cer==1)
    {
        fout<<total<<"\n";
        for(i=1;i<=total;i++)
        {
            for(auto j:cbc[i])
                fout<<j<<" ";
            fout<<"\n";
        }
    }
    else if(cer==2)
    {
        int kon=0;
        for(i=1;i<=n;i++)
            if(art[i]==true)
                kon++;
        fout<<kon<<"\n";
        for(i=1;i<=n;i++)
            if(art[i]==1)
                fout<<i<<" ";
    }
    else
    {
        fout<<punti.size()<<"\n";
        for(auto i:punti)
            fout<<i.first<<" "<<i.second<<"\n";
    }
    return 0;
}