Cod sursa(job #3197055)

Utilizator Stormtrooper-007Vartic Rihard Stormtrooper-007 Data 25 ianuarie 2024 16:15:07
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <bits/stdc++.h>

using namespace std;
const int NMAX=100005;
vector<int>adj[NMAX];
int tin[NMAX];
int low[NMAX],seen[NMAX];
vector<vector<int>>ans;
stack<int>st;
void dfs(int x,int p)
{
    st.push(x);
    low[x]=tin[x]=tin[p]+1;
    seen[x]=1;
    for(int i=0;i<adj[x].size();i++)
    {
        int b=adj[x][i];
        if(seen[b]==1)
        {
            low[x]=min(low[x],tin[b]);
        }
        else
        {
            dfs(b,x);
            low[x]=min(low[x],low[b]);
            vector<int>aux;
            if(tin[x]<=low[b])
            {
                while(st.top()!=b)
                {
                    aux.push_back(st.top());
                    st.pop();
                }
                ans.push_back(aux);
                st.pop();
                ans[ans.size()-1].push_back(b);
                ans[ans.size()-1].push_back(x);
            }
        }
    }
}
int main()
{
    ifstream cin("biconex.in");
    ofstream cout("biconex.out");
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
    {
        if(!seen[i])
        {
            dfs(i,0);
        }
    }
    cout<<ans.size()<<'\n';
    for(int i=0;i<ans.size();i++)
    {
        for(int j=0;j<ans[i].size();j++)
        cout<<ans[i][j]<<" ";
        cout<<'\n';
    }
    return 0;
}