Cod sursa(job #3042303)

Utilizator NiffSniffCojocaru Calin Marcu NiffSniff Data 5 aprilie 2023 15:53:19
Problema Componente biconexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
string file = "biconex";
ifstream cin (file + ".in");
ofstream cout (file + ".out");
const int N = 1e5;
vector <int> a[N+1];
int t_in[N+1],t_min[N+1],timp;
bitset<N+1>articulatie,viz,viz2;
vector <vector<int>> comp;
void dfs (int x, int t = 0)
{
    t_min[x] = t_in[x] = ++timp;
    int nr_fii(0);
    for (auto y : a[x])
    {
        if (t!=y)
        {
            if (t_in[y] == 0) // y este fiu al lui x in arborele DFS
            {
                dfs(y,x);
                t_min[x] = min(t_min[x],t_min[y]);
                nr_fii++;
            }
            else // y este ascendent (indirect) al lui x in arborele DFS
            { // => aceasta muchie este muchie de intoarcere
                t_min[x] = min(t_min[x],t_in[y]);
            }
        }
    }
    if (t_min[x] == t_in[x] || (t == 0 && nr_fii > 1))
    {
        articulatie[x] = 1;
    }
}

void dfs2(int x, int val, vector <int> &v)
{
    v.push_back(x);
    viz[x] = 1;
    for (auto y : a[x])
    {
        if (t_min[y] == val && !viz[y])
        {
            dfs2(y,val,v);
        }
    }
}
int main()
{
    int n,m;
    cin >> n >> m;
    for (int i=0; i<m; i++)
    {
        int x,y;
        cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    for (int i=1; i<=n; i++)
    {
        if (t_in[i] == 0)
        {
            dfs(i,0);
        }
    }
    for (int i=1; i<=n; i++)
    {
        if (!viz[i])
        {
            vector <int> v;
            dfs2(i,t_min[i],v);
            if (v.size() > 1)
            comp.push_back(v);
        }
        viz2[i] = 1;
        for (auto y : a[i])
        {
            if (!viz2[y] && t_min[i] != t_min[y])
            {
                comp.push_back({i,y});
            }
        }
    }
    cout << comp.size() << '\n';
    for (auto v : comp)
    {
        for (auto nod : v)
            cout << nod << ' ';
        cout << '\n';
    }
}