Cod sursa(job #2638937)

Utilizator alex.livadaruLivadaru Alexandru alex.livadaru Data 30 iulie 2020 17:26:55
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>
	
 
	
using namespace std;
	
ifstream r("biconex.in");
	
ofstream w("biconex.out");
	
int n, m, v[100002], h[100002], cnt;
	
vector <int> g[100002], ans[100002];
	
stack <int> st;
	
void dfs(int a, int b)
	
{
	
    v[a] = h[a] = v[b] + 1;
	
    st.push(a);
	
    for(auto it : g[a])
	
        if(it == b)
	
        {
	
            continue;
	
        }
	
        else
	
        {
	
            if(v[it])
	
            {
	
                h[a] = min(h[a], v[it]);
	
                continue;
	
            }
	
 
	
            dfs(it, a);
	
            h[a] = min(h[a], h[it]);
	
            if(v[a] <= h[it])
	
            {
	
                cnt++;
	
                int k;
	
                do
	
                {
	
                    k = st.top();
	
                    st.pop();
	
                    ans[cnt].push_back(k);
	
                }
	
                while(k != it);
	
                ans[cnt].push_back(a);
	
            }
	
        }
	
}
	
int main()
	
{
	
    r>>n>>m;
	
    for(int i = 1; i <= m; i++)
	
    {
	
        int x, y;
	
        r >> x >> y;
	
        g[x].push_back(y);
	
        g[y].push_back(x);
	
    }
	
    for(int i = 1; i <= n; i++)
	
    {
	
        if(!v[i])
	
        {
	
            dfs(i, 0);
	
        }
	
    }
	
    w << cnt<<"\n";
	
    for(int i = 1; i <= cnt; i++)
	
    {
	
        for(auto it : ans[i]){
	
            w << it <<" ";
	
        }
	
        w <<"\n";
	
    }
	
    return 0;
	
}