Cod sursa(job #2670039)

Utilizator iulianarsenoiuArsenoiu Iulian iulianarsenoiu Data 8 noiembrie 2020 19:23:51
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,l[100005],lvl[100005],nr;
bool sel[100005];
stack<pair<int,int>> st;
vector<int> G[100005],rez[100005];
void dfs(int x, int from)
{
    sel[x]=true;
    l[x]=lvl[x];
    for(auto it : G[x])
    {
        if(!sel[it])
        {
            lvl[it]=1+lvl[x];
            st.push({x,it});
            dfs(it,x);
            if(l[x]>l[it])
            {
                l[x]=l[it];
            }
            if(l[it]>=lvl[x])
            {
                ++nr;
                while(!st.empty() && st.top().second!=x)
                {
                    rez[nr].push_back(st.top().second);
                    st.pop();
                }
                rez[nr].push_back(x);
            }
        }
        else if(it!=from)
        {
            l[x]=min(l[x],lvl[it]);
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        if(!sel[i])
        {
            dfs(i,0);
        }
    }
    g<<nr<<'\n';
    for(int i=1;i<=nr;i++)
    {
        sort(rez[i].begin(),rez[i].end());
        for(auto it : rez[i])
        {
            g<<it<<' ';
        }
        g<<'\n';
    }
    return 0;
}