Cod sursa(job #2401623)

Utilizator catalina200029Olteanu Catalina catalina200029 Data 9 aprilie 2019 21:01:28
Problema Componente biconexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.17 kb
#include <bits/stdc++.h>
#define NMAX 100005
#define MMAX 200005

using namespace std;

FILE*f=fopen("biconex.in","r");
FILE*g=fopen("biconex.out","w");

vector<int> a[NMAX];
vector<pair<int,int> > st;

int n,m,d[NMAX],low[NMAX],t[NMAX],nr,nr2,sol[NMAX];

void df(int k) {
    int i,x;
    low[k]=d[k];
    for (i=0;i<a[k].size();i++) {
        x=a[k][i];
        if (!d[x]) {                   ///daca nodul x nu e vizitat
            d[x]=d[k]+1;
            t[x]=k;                    ///k e tatal lui x
            df(x);
            low[k]=min(low[k],low[x]);
            if (low[x]>=d[k]) nr++;    ///k - punct de articulatoe (nu pot sa ajung din x mai sus de k)
        }
        else if (x!=t[k]) low[k]=min(low[k],d[x]);
    }
}

void df2(int k) {
    int i,x,a1,a2,j;
    low[k]=d[k];
    for (i=0;i<a[k].size();i++) {
        x=a[k][i];
        if (x!=t[k] && d[x]<d[k]) st.push_back({x,k});
        if (!d[x]) {                   ///daca nodul x nu e vizitat
            d[x]=d[k]+1;
            t[x]=k;                    ///k e tatal lui x
            df2(x);
            low[k]=min(low[k],low[x]);
            if (low[x]>=d[k]) {        ///k - punct de articulatie (nu pot sa ajung din x mai sus de k)
                nr2=0;
                do {
                    a1=st[st.size()-1].first;
                    a2=st[st.size()-1].second;
                    sol[++nr2]=a1;
                    sol[++nr2]=a2;
                    st.pop_back();
                } while (!st.empty() && !(a1==x && a2==k || a1==k && a2==x));
                sort(sol+1,sol+nr2+1);
                for (j=1;j<=nr2;j++)
                    if (sol[j]!=sol[j-1]) fprintf(g,"%d ",sol[j]);
                fprintf(g,"\n");
            }
        }
        else if (x!=t[k]) low[k]=min(low[k],d[x]);
    }
}

void init() {
    int i;
    for (i=1;i<=n;i++)
        d[i]=low[i]=t[i]=0;
}

int main() {
    int i,j,x,y;
    fscanf(f,"%d%d",&n,&m);
    for (i=1;i<=m;i++) {
        fscanf(f,"%d%d",&x,&y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    d[1]=1;
    df(1);
    fprintf(g,"%d\n",nr);
    init();
    df2(1);
    return 0;
}