Cod sursa(job #2744263)

Utilizator MateGMGozner Mate MateGM Data 24 aprilie 2021 10:50:44
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

#define nmax 100005

stack<pair<int,int> >stk;
vector<vector<int> >comp;
bool visited[nmax];
int low[nmax];
int depth[nmax];

void add(int x, int y) {

    int a,b;
    vector<int> c;
    do {
        a = stk.top().first;
        b = stk.top().second;
        c.push_back(a);
        c.push_back(b);
        stk.pop();

    } while(!stk.empty() && (a != x || b != y));
    sort(c.begin(), c.end());
    comp.push_back(c);

}

void art_point(vector<vector<int>>&adj,int i,int f)
{
    visited[i]=true;
    low[i]=depth[i]=depth[f]+1;

    for(auto ni :adj[i])
    {
        if (!visited[ni])
        {
            stk.push({i,ni});
            art_point(adj,ni,i);
            if(low[ni]>=depth[i])
                add(i,ni);
            low[i]=min(low[i],low[ni]);
        }
        else if(ni!=f)
            low[i]=min(low[i],depth[ni]);
    }


}

int main()
{
    ifstream be("biconex.in");
    ofstream ki("biconex.out");
    int n,m;
    be>>n>>m;
    vector<vector<int> > adj(n+1);
    for(int i=0;i<m;i++)
    {
        int x,y;
        be>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
        if(!visited[i])
            art_point(adj,i,0);
    ki<<comp.size()<<'\n';
    for(auto ni : comp)
    {
        for(int i=0;i<ni.size();i++)
        {
            if(i==0 || ni[i]!=ni[i-1])
                ki<<ni[i]<<" ";
        }
        ki<<'\n';
    }
    return 0;
}