Cod sursa(job #2967835)

Utilizator DKMKDMatei Filibiu DKMKD Data 20 ianuarie 2023 09:22:59
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define imax INT_MAX
#define llmax LLONG_MAX
#define sz(x) (int((x).size()))
#define start ios_base::sync_with_stdio(false), cin.tie(0)
#define finish fin.close(), fout.close()s
using namespace std;

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

int n, m;
int d[100005], low[100005];

vector<int> s;

vector<int> adj[100005];
vector<vector<int> > ans;

int t;

void dfs(int nod, int dad)
{
    d[nod] = low[nod] =  ++t;
    s.pb(nod);

    for(auto i : adj[nod])
    {
        if(i == dad) continue;

        if(d[i] > 0) low[nod] = min(low[nod], d[i]);
        else
        {
            dfs(i, nod);
            low[nod] = min(low[nod], low[i]);

            if(low[i] >= d[nod])
            {
                vector<int> x;

                while(s.back() != i)
                {
                    x.pb(s.back());
                    s.pop_back();
                }
                x.pb(s.back());
                s.pop_back();

                x.pb(nod);
                reverse(all(x));
                ans.pb(x);
            }
        }
    }
}

int main()
{
	start;

    int x, y;

    fin >> n >> m;

    for(int i = 1; i <= m; ++i)
    {
        fin >> x >> y;
        adj[x].pb(y);
        adj[y].pb(x);
    }

    for(int i = 1; i <= n; ++i)
        if(d[i] == 0)
            dfs(i, 0);

    fout << ans.size() << '\n';

    for(auto i : ans){
        for(auto j : i)
            fout << j << ' ';
        fout << '\n';
    }
	finish;
	return 0;
}