Cod sursa(job #2359503)

Utilizator BotzkiBotzki Botzki Data 28 februarie 2019 21:33:03
Problema Componente biconexe Scor 28
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.23 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX=10000;
vector <int>G[NMAX+5];
vector <int>dfs_discover, dfs_low, articulation_vertex, dfs_parent;
set <int>componente_biconexe[NMAX+5];
set <int>::iterator it;
struct muchie
{
    int nod1, nod2;
};
muchie st[NMAX+5];
int top;
int timp, dfsRoot, rootChildren, n, nr;
void articulationPoint(int u)
{
    int v, j;
    muchie aux;
    timp++;
    dfs_discover[u]=dfs_low[u]=timp;
    for(j=0;j<G[u].size();j++)
    {
        v=G[u][j];
        if(!dfs_discover[v])
        {
            ///formez componenta biconexa
          aux.nod1=u;
          aux.nod2=v;
          st[++top]=aux;
          dfs_parent[u]=v;
          if(u==dfsRoot)
             rootChildren++;
          articulationPoint(v);
          if(dfs_low[v]>=dfs_discover[u])
             {
                 articulation_vertex[u]=1;
                 ///bag in solutie componenta biconexa;
                 nr++;
                 while(top>0)
                 {
                    componente_biconexe[nr].insert(st[top].nod1);
                    componente_biconexe[nr].insert(st[top].nod2);
                    top--;
                 }
             }
          dfs_low[u]=min(dfs_low[u], dfs_low[v]);
        }
        else
        {
            if(dfs_parent[u]!=v)
                dfs_low[u]=min(dfs_low[u], dfs_discover[v]);
        }
    }
}
int main()
{

    int m, u, v, i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs_parent.assign(n+1, 0);
    dfs_low.assign(n+1, 0);
    dfs_discover.assign(n+1, 0);
    articulation_vertex.assign(n+1, 0);
    for(i=1;i<=n;i++)
    {
        if(dfs_discover[i]==0)
        {
            dfsRoot=i;
            rootChildren=0;
            articulationPoint(i);
            articulation_vertex[dfsRoot]=(rootChildren>1);
        }
    }
  fout<<nr<<"\n";
  for(i=1;i<=nr;i++)
  {
      for(it=componente_biconexe[i].begin();it!=componente_biconexe[i].end();it++)
          fout<<(*it)<<" ";
      fout<<"\n";
  }

    return 0;
}