Cod sursa(job #2359917)

Utilizator BotzkiBotzki Botzki Data 1 martie 2019 10:36:58
Problema Componente biconexe Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX=100000;
vector <int>G[NMAX+5];
vector <int>dfs_discover, dfs_low, dfs_parent;
set<int>componente_biconexe[NMAX+5];
set<int>::iterator it;
struct muchie
{
    int nod1, nod2;
};
stack <muchie>st;
int timp, n, nr;
void componenta(int x, int y)
{
    int i, j;
    nr++;
    do
    {
        i=st.top().nod1;
        j=st.top().nod2;
        st.pop();
        componente_biconexe[nr].insert(j);
        componente_biconexe[nr].insert(i);
    }while(i!=x or j!=y);
}
void DFS(int nod)
{
    int fiu, j;
    muchie aux;
    timp++;
    dfs_discover[nod]=dfs_low[nod]=timp;
    for(j=0;j<G[nod].size();j++)
    {
        fiu=G[nod][j];
        if(dfs_parent[fiu]!=nod)
        {
            if(!dfs_discover[fiu])
            {
              aux.nod1=nod;
              aux.nod2=fiu;
              st.push(aux);
              dfs_parent[fiu]=nod;
              DFS(fiu);
              if(dfs_low[fiu]>=dfs_discover[nod])
              {
                 ///nod este punct de articulatie
                 ///formez componenta biconexa
                 componenta(nod, fiu);
              }
              dfs_low[nod]=min(dfs_low[nod], dfs_low[fiu]);
            }
            else
              dfs_low[nod]=min(dfs_low[nod], dfs_discover[fiu]);
        }
    }
}
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);
    for(i=1;i<=n;i++)
    {
        if(dfs_discover[i]==0)
            DFS(i);
    }
  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;
}