Cod sursa(job #2381226)

Utilizator Alex.PAlexandru Pacurar Alex.P Data 16 martie 2019 12:17:36
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <bits/stdc++.h>
#define nmax 100001

using namespace std;

vector <int> G[nmax];
int d[nmax];
int l[nmax];
bool seen[nmax];
bool articulation[nmax];
vector <int> q;
vector <int> sol[nmax];
int nrsol;

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()!=dest){
            sol[nrsol].push_back(q.back());
            q.pop_back();
        }
        sol[nrsol].push_back(q.back());
        q.pop_back();
        sol[nrsol].push_back(node);
        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()
{
    FILE *fin, *fout;
    fin=fopen("biconex.in","r");
    fout=fopen("biconex.out","w");
    int n,m,i,j;
    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");
    }
//    fprintf(fout,"\n");
//    for(i=1;i<=n;i++){
//        if(articulation[i])
//            fprintf(fout,"%d ",i);
//    }
    fclose(fin);
    fclose(fout);
    return 0;
}