Cod sursa(job #2295220)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 3 decembrie 2018 13:14:10
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <cstdio>
#include <vector>
#define DIM 100001
using namespace std;
int low[DIM],niv[DIM],f[DIM],st[DIM],elem,sol;
vector <int> v[DIM],s[DIM];
void dfs (int nod,int tata){
    int i,vecin;
    low[nod]=niv[nod];
    st[++elem]=nod;
    for (i=0;i<v[nod].size();i++){
        vecin=v[nod][i];
        if (vecin!=tata){
            if (!niv[vecin]){
                niv[vecin]=1+niv[nod];
                dfs (vecin,nod);
                low[nod]=min(low[nod],low[vecin]);
                ///VERIFICARE
                if (low[vecin]>=niv[nod]){
                    sol++;
                    do{
                        s[sol].push_back(st[elem]);
                        elem--;
                    }while (st[elem+1]!=vecin);
                    s[sol].push_back(nod);
                }
            }
            else low[nod]=min(low[nod],niv[vecin]);
        }
    }
}
int main()
{
    FILE *fin=fopen ("biconex.in","r");
    FILE *fout=fopen ("biconex.out","w");
    int n,m,x,y,i,j;
    fscanf (fin,"%d%d",&n,&m);
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for (i=1;i<=n;i++){
        if (!niv[i]){
            niv[i]=1;
            dfs (i,0);
        }
    }
    fprintf (fout,"%d\n",sol);
    for (i=1;i<=sol;i++){
        for (j=0;j<s[i].size();j++)
            fprintf (fout,"%d ",s[i][j]);
        fprintf (fout,"\n");
    }
    return 0;
}