Cod sursa(job #2380570)

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

using namespace std;

vector <int> G[nmax];
//int coada[nmax][2];
//int low[nmax];
//int vizit[nmax];
//int depth[nmax];
//int k=0;
//int count=0;
//vector <int> p[nmax];
int d[nmax];
int l[nmax];
bool seen[nmax];
bool articulation[nmax];
vector <int> q;
vector <int> sol[nmax];
int nrsol;

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]);
//        }
//    }
//}

void get_articulation(int node, int depth, int father){
  q.push_back(node);
  seen[node]=true;
  d[node]=depth;
  l[node]=depth;
  bool is_art=false;
  int child=0;
  for(int i=0;i<G[node].size();i++){
    int dest=G[node][i];
    if(!seen[dest]){
      get_articulation(dest, depth+1, node);
      child++;
      if(l[dest]>=d[node]){
        is_art=true;
        while(q.back()!=node){
            sol[nrsol].push_back(q.back());
            q.pop_back();
        }
        sol[nrsol].push_back(q.back());
        nrsol++;
      }
      l[node]=min(l[node], l[dest]);
    }else{
      if(dest!=father){
        l[node]=min(l[node],l[dest]);
      }
    }
  }
  if( (is_art && father!=0) || (father==0 && child>1)){
    articulation[node]=true;
  }
}

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);
        G[i].push_back(j);
        G[j].push_back(i);
    }
    get_articulation(1,1,0);
    fprintf(fout,"%d\n",nrsol);
    for(i=0;i<nrsol;i++){
        for(j=0;j<sol[i].size();j++){
            fprintf(fout,"%d ",sol[i][j]);
        }
        fprintf(fout,"\n");
    }
    fclose(fin);
    fclose(fout);
    return 0;
}