Cod sursa(job #3226327)

Utilizator AndreiBOTOBotocan Andrei AndreiBOTO Data 20 aprilie 2024 22:43:45
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.63 kb
#include <bits/stdc++.h>

#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

///#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;

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

stack<int>stiva;

bool art[NMAX];
int tmin[NMAX];
int ti[NMAX];

int total;
int kon;
int n;

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


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n,i,m,task=1;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        int x,y;
        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(task==1)
    {
        cout<<total<<"\n";
        for(i=1;i<=total;i++)
        {
            for(auto it:cbc[i])
                cout<<it<<" ";
            cout<<"\n";
        }
    }
    else if(task==2)
    {
        int saiz=0;
        for(i=1;i<=n;i++)
            if(art[i])
                saiz++;
        cout<<saiz<<"\n";
        for(i=1;i<=n;i++)
            if(art[i])
                cout<<i<<" ";
    }
    else
    {
        cout<<punti.size()<<"\n";
        for(auto it:punti)
            cout<<it.first<<" "<<it.second<<"\n";
    }
    return 0;
}