Cod sursa(job #2410536)

Utilizator mateibanuBanu Matei Costin mateibanu Data 20 aprilie 2019 10:07:31
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <bits/stdc++.h>

using namespace std;

#define NMAX 100010

stack<pair<int,int> >s;

vector<int>v[NMAX],r[NMAX];

int viz[NMAX],low[NMAX],niv[NMAX],t[NMAX];
int rnr,n,m;
pair<int,int>p;

void df(int o){
    viz[o]=1;
    low[o]=niv[o];
    int nr=v[o].size();
    for (int i=0;i<nr;i++){
        int f=v[o][i];
        if (f!=t[o]&&niv[o]>niv[f]) s.push(make_pair(o,f));
        if (!viz[f]){
            t[f]=o;
            niv[f]=niv[o]+1;
            df(f);
            low[o]=min(low[o],low[f]);
            if (low[f]>=niv[o]){
                rnr++;
                p=s.top();
                r[rnr].push_back(p.first);
                r[rnr].push_back(p.second);
                s.pop();
                while ((p.first!=o||p.second!=f)&&(p.first!=f||p.second!=o)){
                    p=s.top();
                    r[rnr].push_back(p.first);
                    r[rnr].push_back(p.second);
                    s.pop();
                }
            }
        }
        else
        if (f!=t[i]){
            low[o]=min(low[o],niv[f]);
        }
    }

}

int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    int i,x,y;
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    niv[1]=1;
    df(1);
    printf("%d\n",rnr);
    for (i=1;i<=rnr;i++){
        sort(r[i].begin(),r[i].end());
        int nr=r[i].size();
        for (int j=0;j<nr;j++){
            if (j==0||r[i][j-1]!=r[i][j]) printf("%d ",r[i][j]);
        }
        printf("\n");
    }
    return 0;
}