Cod sursa(job #3003871)

Utilizator AndreiCroitoruAndrei Croitoru AndreiCroitoru Data 15 martie 2023 23:25:11
Problema Componente biconexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.34 kb
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 1;
vector <int> g[N];
pair <int, int> dist[N];
int parent[N];
bool verif[N];
bool used[N];
int k = 0, ans = 1;

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

stack <pair<int, int>> muchii;
void afis(pair <int, int> muchie)
{

    set <int> sol;
    while(!muchii.empty())
    {
        pair<int, int> aux = muchii.top();

        sol.insert(aux.first);
        sol.insert(aux.second);
        if(aux == muchie)
        {
            muchii.pop();
            break;
        }
        muchii.pop();
    }
    for(auto it : sol)
        out << it << " ";
    out << '\n';
}

void dfs_noprint(int node)
{
    verif[node] = 1;
    int copii = 0;
    dist[++k].first = k;
    dist[k].second = k;
    for(auto next : g[node])
    {
        pair <int, int> muchie = {node, next};
        if(!verif[next])
        {
            copii ++;

            parent[next] = node;

            muchii.push(muchie);
            dfs_noprint(next);
            dist[node].second = min(dist[node].second, dist[next].second);
            if(!parent[node] and copii > 1)
            {
                ans ++;
//                afis(muchie);
            }
            if(parent[node] and dist[next].second >= dist[node].first)
            {
                ans ++;
//                afis(muchie);
            }
        }
        else if(parent[node] != next and dist[next].first < dist[node].second)
        {
            dist[node].second = dist[next].first;
            muchii.push(muchie);
        }
    }
}


void dfs(int node)
{
    verif[node] = 1;
    int copii = 0;
    dist[++k].first = k;
    dist[k].second = k;
    for(auto next : g[node])
    {
        pair <int, int> muchie = {node, next};
        if(!verif[next])
        {
            copii ++;

            parent[next] = node;

            muchii.push(muchie);
            dfs(next);
            dist[node].second = min(dist[node].second, dist[next].second);
            if(!parent[node] and copii > 1)
            {
                ans ++;
                afis(muchie);
            }
            if(parent[node] and dist[next].second >= dist[node].first)
            {
                ans ++;
                afis(muchie);
            }
        }
        else if(parent[node] != next and dist[next].first < dist[node].second)
        {
            dist[node].second = dist[next].first;
            muchii.push(muchie);
        }
    }
}


int n;
void print_biconnected_component()
{
    set <int> sol;
    for(int i=1; i<=n; i++)
    {
        if(!used[i])
        {

            dfs(i);
            while(!muchii.empty())
            {

                pair <int , int> aux = muchii.top();
                sol.insert(aux.first);
                sol.insert(aux.second);
                muchii.pop();
            }
        }
    }
    for(auto it : sol)
        out << it << " ";
}

int main()
{


    int m;
    in >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int a, b;
        in >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs_noprint(1);
    out << ans << '\n';
    memset(verif, 0, N);
    while(!muchii.empty())
        muchii.pop();
    print_biconnected_component();
    return 0;
}