Cod sursa(job #1574828)

Utilizator sfechisalin@yahoo.comSfechis Alin [email protected] Data 20 ianuarie 2016 21:20:20
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>
#define NN 100005
#define pa pair<int,int>
#define ff first
#define ss second
#define mkp make_pair
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
using VI=vector<int>;
VI G[NN];
vector<VI> answ;
VI aux;
stack<pa>S;
int n,m,nivel[NN],L[NN],t[NN],x1,x2;
bool viz[NN];
void read()
{
    fin>>n>>m;
    for(int x,y;m;--m)
    {
        fin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}
void DFS(int nod,int niv)
{
    viz[nod]=true;
    nivel[nod]=L[nod]=niv;
    for(const int &f:G[nod])
    {
        if(f==t[nod])
            continue;
         if(!viz[f])
         {
           S.push(mkp(nod,f));
           t[f]=nod;
           DFS(f,niv+1);
           L[nod]=min(L[nod],L[f]);
           if(L[f]>=nivel[nod])
           {
               aux.clear();
               while (true)
				{
					x1 = S.top().first;
					x2 = S.top().second;
					aux.push_back(x1);aux.push_back(x2);
					S.pop();
					if (x1 == nod && x2 == f)
						break;
				}
                answ.push_back(aux);
           }
         }
         else
            L[nod]=min(L[nod],nivel[f]);

    }
}
int main()
{
    read();
    DFS(1,1);
    fout<<answ.size()<<"\n";
    for(auto aux1:answ)
    {
        sort(aux1.begin(),aux1.end());
        aux1.erase(unique(aux1.begin(), aux1.end()), aux1.end());
        for(auto i:aux1)
            fout<<i<<" ";
        fout<<"\n";
    }
}