Cod sursa(job #1610301)

Utilizator PetrutiuPaulPetrutiu Paul Gabriel PetrutiuPaul Data 23 februarie 2016 13:47:04
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;

    ifstream fin("biconex.in");
    ofstream fout("biconex.out");

stack <int> s;
vector <int> v[100005],rasp[100006];
int nivel[100005];
int low[100005];

int n,m,cbc;

void scoate(int nod, int next)
{

      while(s.top() != next)
      {
          rasp[cbc].push_back(s.top());
          s.pop();
      }
     s.pop();
     rasp[cbc].push_back(nod);
     rasp[cbc].push_back(next);
}

void DFS(int nod, int k)
{
    nivel[nod]=low[nod]=k;

    for(int i=0;i<v[nod].size();i++)
    {
        if(!nivel[v[nod][i]])
        {
            s.push(v[nod][i]);
            DFS(v[nod][i],k+1);
            low[nod]=min(low[nod],low[v[nod][i]]);
            if(low[v[nod][i]]>=nivel[nod])
            {
                cbc++;
                scoate(nod,v[nod][i]);
            }
        }
        else
            low[nod]=min(low[nod],nivel[v[nod][i]]);
    }

}


int main()
{
    int x,y;

    fin>>n>>m;

    for(int i=1;i<=m;i++)
    {

        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    s.push(1);

    DFS(1,1);

    fout<<cbc<<"\n";

    for(int i=1; i<=cbc; i++)
    {
        for(int j=0; j<rasp[i].size(); j++)
        fout<<rasp[i][j]<<" ";
        fout<<"\n";
    }
}