Cod sursa(job #1787386)

Utilizator PaulStighiStiegelbauer Paul-Alexandru PaulStighi Data 24 octombrie 2016 16:45:59
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

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

const int NMax = 100005;

int N,M,K;
bool Use[NMax],Critical[NMax];
int Level[NMax],Low[NMax];

stack <int> S1,S2;
vector <int> G[NMax],CB[2*NMax];

void Read()
{
  fin>>N>>M;
  for(int i = 1; i <= M; i++)
      {
        int x,y;
        fin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
      }
}

void Sol(int x,int y)
{
    int nod1,nod2;
    nod1 = nod2 = 0;

    while(nod1 != x && nod2 != y)
    {
        nod1 = S1.top();
        nod2 = S2.top();
        CB[K].push_back(nod1);
        CB[K].push_back(nod2);
        S1.pop();
        S2.pop();
    }
}

void DFS(int Nod, int Father)
{
  Use[Nod] = 1;
  Level[Nod] = Level[Father] + 1;
  Low[Nod] = Level[Nod];

  for(int i = 0 ; i < (int)G[Nod].size(); ++i)
      {
        int Vecin = G[Nod][i];

        if(Vecin == Father)
            continue;
        if(!Use[Vecin])
        {
            S1.push(Nod);
            S2.push(Vecin);

            DFS(Vecin,Nod);

            Low[Nod] = min(Low[Nod],Low[Vecin]);

            if(Low[Vecin] >= Level[Nod])
            {   K++;    Sol(Nod,Vecin); }
        }
        else
          Low[Nod] = min(Low[Nod],Level[Vecin]);
      }
}

void Print()
{
    fout<<K<<"\n";

    for(int i = 1 ; i <= K ; ++i)
    {
        sort(CB[i].begin(),CB[i].end());

        CB[i].erase( unique( CB[i].begin() , CB[i].end() ) , CB[i].end() );

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

int main()
{
    Read();
    DFS(1,0);
    Print();
    return 0;
}