Cod sursa(job #2685575)

Utilizator SochuDarabaneanu Liviu Eugen Sochu Data 17 decembrie 2020 11:41:43
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <bits/stdc++.h>
//#pragma GCC optimize ("03")
#define FastIO ios_base::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define FILES freopen("biconex.in" , "r" , stdin) , freopen("biconex.out" , "w" , stdout)
#define pii pair < int , int >
#define pb push_back

using namespace std;

const int N = 1e5 + 10;

int n , m , x , y;
vector < int > v[N] , compbi[N];
stack < pii > s;
int h[N] , low[N];
bool mark[N];

int cnt;

void comp(pii t)
{
    ++cnt;

    while(s.top() != t)
    {
        compbi[cnt].pb(s.top().second);
        s.pop();
    }

    compbi[cnt].pb(s.top().first);
    compbi[cnt].pb(s.top().second);
    s.pop();
}

void dfs(int w , int p , int height)
{
    mark[w] = 1;
    h[w] = height;
    low[w] = height;

    for(auto i : v[w])
        if(!mark[i])
        {
            s.push({w , i});
            dfs(i , w , height + 1);
            low[w] = min(low[w] , low[i]);

            if(p == -1 && v[w].size() > 1)
                comp({w , i});
            else if(low[i] >= height)
                comp({w , i});
        }
        else if(i != p)
            low[w] = min(low[w] , low[i]);
}

signed main()
{
	#ifndef ONLINE_JUDGE
		FastIO , FILES;
	#endif

    cin >> n >> m;

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

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

    cout << cnt << '\n';

    for(int i = 1 ; i <= cnt ; i++ , cout << '\n')
        for(auto j : compbi[i])
            cout << j << ' ';

    return 0;
}