Cod sursa(job #2380563)

Utilizator Alex.PAlexandru Pacurar Alex.P Data 15 martie 2019 10:38:52
Problema Componente biconexe Scor 64
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#define nmax 100001

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;
    for(int i=0;i<v[node].size();i++){
        int vecin=v[node][i];
        if(!vizit[vecin] && vecin!=father){
            coada[k][0]=node;
            coada[k][1]=vecin;
            k++;
            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]);
        }
    }
}

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,1);
    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;
}