Cod sursa(job #3041600)

Utilizator AndreiBOTOBotocan Andrei AndreiBOTO Data 31 martie 2023 19:39:23
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.3 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>

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

using namespace std;

#define cin fin
#define cout fout

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]=kon;
    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(stiva.top());
                    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;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>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)
    {
        cout<<total<<"\n";
        for(i=1;i<=total;i++)
        {
            for(auto j:cbc[i])
                cout<<j<<" ";
            cout<<"\n";
        }
    }
    else if(cer==2)
    {
        int kon=0;
        for(i=1;i<=n;i++)
            if(art[i]==true)
                kon++;
        cout<<kon<<"\n";
        for(i=1;i<=n;i++)
            if(art[i]==1)
                cout<<i<<" ";
    }
    else
    {
        cout<<punti.size()<<"\n";
        for(auto i:punti)
            cout<<i.first<<" "<<i.second<<"\n";
    }
    return 0;
}