Cod sursa(job #2114827)

Utilizator stefzahZaharia Stefan Tudor stefzah Data 25 ianuarie 2018 21:50:17
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int N,M,i,j,x,y,p,ct,s[100005],niv[100005],nm[100005],k,ck[100005];
vector <int> v[100005],sol[100005];
void DFS(int nod)
    {int y,i;
     for(i=0;i<v[nod].size();i++)
        {y=v[nod][i];
         if(!niv[y])
           {ck[nod]=k;
            niv[y]=nm[y]=niv[nod]+1;
            DFS(y);
            nm[nod]=min(nm[nod],nm[y]);
            if(niv[nod]==nm[y])
            {ct++;
             //fout<<nod<<" "<<y<<" "<<k<<" "<<ck[nod]<<"\n";
             while(k>ck[nod])
                  {sol[ct].push_back(s[k]);
                   k--;
                  }
             sol[ct].push_back(nod);
            }
           }
         else nm[nod]=min(nm[nod],niv[y]);

        }
        k++;
     s[k]=nod;
    }
int main()
{int i,j;
 fin>>N>>M;
 for(i=1;i<=M;i++)
    {fin>>x>>y;
     v[x].push_back(y);
     v[y].push_back(x);
    }
 niv[1]=1;nm[1]=1;
 DFS(1);
 fout<<ct<<"\n";
 for(i=1;i<=ct;i++)
 {for(j=0;j<sol[i].size();j++)
     fout<<sol[i][j]<<" ";
  fout<<"\n";
 }

 }