Cod sursa(job #2746359)

Utilizator cristia_razvanCristia Razvan cristia_razvan Data 27 aprilie 2021 18:51:35
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <bits/stdc++.h>
using namespace std;
 
#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()
 
 
using ll = long long;
using uint = unsigned int;
 
const string filename = "biconex";
 
fstream fin(filename + ".in");
ofstream fout(filename + ".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;	
}