Cod sursa(job #2189514)

Utilizator PinkiePie1189Preoteasa Mircea-Costin PinkiePie1189 Data 28 martie 2018 15:31:49
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.39 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#define MAXV 100000
#define MAXE 500000

void dfs(int nod);

FILE*fin,*fout;

int lista[MAXV+1],next[MAXE+1],val[MAXE+1],k=0;
int st[MAXE+1],ult=-1;

std::pair<int,int> edge[MAXE+1];
std::vector<std::vector<int>> sol;
std::vector<int> partial_sol;
int level[MAXV+1],ind[MAXV+1];
int tata[MAXV+1];
int index=0;
int main()
{
    fin=fopen("biconex.in","r");
    fout=fopen("biconex.out","w");

    int V,E;


    fscanf(fin,"%d%d",&V,&E);

    for(int i=1; i<=E; i++)
    {
        int x,y;
        fscanf(fin,"%d%d",&x,&y);
        next[++k]=lista[y];
        val[k]=x;
        lista[y]=k;
        next[++k]=lista[x];
        val[k]=y;
        lista[x]=k;
    }
    /*for(int i=1;i<=V;i++)
    {
        if(ind[i]==0)
        {
            dfs(i);
        }
    }*/
    dfs(1);
    fprintf(fout,"%d\n",sol.size());
    for(int i=0;i<sol.size();i++)
    {
        for(int j=0;j<sol[i].size();j++)
        {
            fprintf(fout,"%d ",sol[i][j]);
        }
        fprintf(fout,"\n");
    }
    /*fprintf(fout, "\n\n\n\n\n-----------\n");
    for(int i = 1; i <= V; i++)
        fprintf(fout, "%d ", level[i]);*/
    fclose(fin);
    fclose(fout);
}

void dfs(int nod)
{
    ind[nod]= ind[tata[nod]] + 1;
    level[nod]=ind[nod];
    int p=lista[nod];
    while(p!=0)
    {
        int vec=val[p];
        if(tata[nod] != vec){
            if(ind[vec]==0)
            {
                st[++ult]=p;
                tata[vec]=nod;
                dfs(vec);
                level[nod]=std::min(level[nod],level[vec]);
                if(ind[nod]<=level[vec])
                {
                    partial_sol.resize(0);
                    while(ult>0  && st[ult]!=p)
                    {
                        partial_sol.push_back(val[st[ult]]);
                        //printf("%d ",val[st[ult]]);
                        ult--;
                    }
                    partial_sol.push_back(val[p]);
                    //printf("%d ",val[p]);
                    ult--;
                    partial_sol.push_back(nod);
                    //printf("%d\n",nod);
                    sol.push_back(partial_sol);
                }

            }
            else
            {
                level[nod]=std::min(level[nod],ind[vec]);
            }
        }
        p=next[p];
    }
}