Cod sursa(job #2272205)

Utilizator alex_bb8Banilean Alexandru-Ioan alex_bb8 Data 29 octombrie 2018 20:22:47
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <bits/stdc++.h>
using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

vector <int> G[100003],bic[100003];
stack <pair<int,int> >st;
int n,m,p,x,y,nr,lvl[100003],low[100003],k;

void compbic(int x,int y)
{

   int tx,ty;
   ++k;
   do
   {
      tx=st.top().first;
      ty=st.top().second;
      st.pop();
      bic[k].push_back(tx);
      bic[k].push_back(ty);
   } while(tx!=x  ||  ty!=y) ;


}

void DFS(int node,int t)
{
   lvl[node]=lvl[t]+1;
   low[node]=lvl[node];
   for(int u=0;u<G[node].size();++u)
   {
      int w=G[node][u];
      if(w!=t)
      {
         if(!lvl[w])
         {
            st.push(make_pair(node,w));
            DFS(w,node);
            low[node]=min(low[node],low[w]) ;
            if(node==1)  nr++;
            if(low[w]>=lvl[node] )
            {
            compbic(node,w);
            }
         }
         else
            low[node]=min(low[node],lvl[w]);
      }
   }
}

int main()
{
    f>>n>>m;
  for(int i=1;i<=m;i++)
  {
    f>>x>>y;
    G[x].push_back(y);
    G[y].push_back(x);
   }

    DFS(1,0);

    g<<k<<"\n";
      for(int i=1;i<=k;i++)
      {
        sort(bic[i].begin(),bic[i].end());
        vector <int >::iterator it;
        it=unique(bic[i].begin(),bic[i].end());
        bic[i].resize(distance(bic[i].begin(),it));
         for(int j=0;j<bic[i].size();++j)
          g<<bic[i][j]<<" ";
          g<<"\n";
      }
    return 0;
}