Cod sursa(job #2292921)

Utilizator tavi255Varzaru Octavian Stefan tavi255 Data 30 noiembrie 2018 11:26:12
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
//#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int Max=100005;
int viz[Max],nivel[Max],nma[Max],n,m,c;
vector < int >v[Max],comp[Max];
stack <int >s;
void citire()
{
   in>>n>>m;
   for(int i=1;i<=m;i++)
   {
       int x,y;
       in>>x>>y;
       v[x].push_back(y);
       v[y].push_back(x);
   }
}
void dfs(int nod,int tata)
{
    viz[nod]=1;
    s.push(nod);
    nivel[nod]=nivel[tata]+1;
    nma[nod]=nivel[nod];
    for(int j=0;j<v[nod].size();j++)
    {
        int fiu=v[nod][j];
        if(fiu!=tata)
        {
            if(viz[fiu]==1)
            {
                if(nma[nod]>nivel[fiu])
                nma[nod]=nivel[fiu];
            }

            else
            {
                 dfs(fiu,nod);
                  if(nma[nod]>nma[fiu])
                    nma[nod]=nma[fiu];
                 //   if(nivel[nod]<=nma[fiu] && nod!=1)
                  //  cout<<nod<<" ";
                  if(nivel[nod]<=nma[fiu])
                  {
                      c++;
                       while(s.top()!=fiu)
                      {
                       comp[c].push_back(s.top());
                        s.pop();
                      }
                     comp[c].push_back(fiu);
                     s.pop();
                     comp[c].push_back(nod);
                  }

            }

        }
    }

}
int main()
{
     citire();
    for(int i=1;i<=n;i++)
        if(!viz[i])
        dfs(i,0);
        out<<c<<"\n";
        for(int i=1;i<=c;i++)
        {
            for(int j=0;j<comp[i].size();j++)
                out<<comp[i][j]<<" ";
                 out<<"\n";
        }
    return 0;
}