Cod sursa(job #2203395)

Utilizator Alex.PAlexandru Pacurar Alex.P Data 12 mai 2018 10:43:41
Problema Componente biconexe Scor 64
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#define nmax 100000

using namespace std;

vector <int> v[nmax];
int coada[nmax][2];
int low[nmax];
int vizit[nmax];
int depth[nmax];
int k=0;
int count=0;
vector <int> p[nmax];

FILE *fin, *fout;

void bi(int node, int father, int d){
    low[node]=depth[node]=d;
    vizit[node]=1;
    int x=0;
    for(int i=0;i<v[node].size();i++){
        int vecin=v[node][i];
        if(!vizit[vecin]){
            coada[k][0]=node;
            coada[k][1]=vecin;
            k++;
            x++;
            bi(vecin,node,d+1);
            low[node]=min(low[node],low[vecin]);
            if(depth[node]<=low[vecin]){
                k--;
                p[count].push_back(coada[k][1]);
                while(coada[k][0]!=node){
                    p[count].push_back(coada[k][0]);
                    k--;
                }
                p[count].push_back(coada[k][0]);
                count++;
            }
        }else if(vecin!=father){
            low[node]=min(low[node],depth[vecin]);
        }
    }
    printf("node : %d - %d %d\n",node,depth[node],low[node]);
}

int main()
{
    int n,m,i,j;
    fin=fopen("biconex.in","r");
    fout=fopen("biconex.out","w");
    fscanf(fin,"%d%d",&n,&m);
    for(m;m>0;m--){
        fscanf(fin,"%d%d",&i,&j);
        v[i].push_back(j);
        v[j].push_back(i);
    }
    bi(1,-1,0);
    if(k>1){
      p[count].push_back(coada[k][1]);
      while(k>1){
          p[count].push_back(coada[k][0]);
          k--;
          count++;
      }
    }
    fprintf(fout,"%d\n",count);
    for(i=0;i<count;i++){
        for(j=0;j<p[i].size();j++){
            fprintf(fout,"%d ",p[i][j]);
        }
        fprintf(fout,"\n");
    }
    fclose(fin);
    fclose(fout);
    return 0;
}