Cod sursa(job #2408107)

Utilizator UnseenMarksmanDavid Catalin UnseenMarksman Data 17 aprilie 2019 17:05:01
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

const int maxn = 2e5+2;
int n, m, level[maxn], low[maxn], st;
pair<int, int>stk[maxn*2];
vector<int>G[maxn];
vector<vector<int> >R;

void sterge(int nod1, int nod2)
{
    vector<int>comp;int x, y;
    do
    {
        x=stk[st].first;
        y=stk[st].second;
        st--;
        comp.push_back(x);
        comp.push_back(y);
    }while(x!=nod1 || y!=nod2);
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(),comp.end()), comp.end());
    R.push_back(comp);
}

void dfs(int nod, int tata, int nivel)
{
    level[nod]=low[nod]=nivel;
    for(auto it:G[nod])
    {
        if(it!=tata)
        {
            if(level[it]==0)
            {
                ++st;
                stk[st].first=nod;
                stk[st].second=it;
                dfs(it, nod, nivel+1);
                low[nod]=min(low[nod], low[it]);
                if(low[it]>=level[nod])
                {
                    sterge(nod, it);
                }
            }
            else
            {
                low[nod]=min(low[nod], level[it]);
            }
        }
    }
}

int main()
{
    int x, y;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1, 0, 1);
    fout<<R.size()<<'\n';
    for(int i=0; i<R.size(); i++)
    {
        for(auto it:R[i])
        {
            fout<<it<<' ';
        }
        fout<<'\n';
    }
    return 0;
}