Cod sursa(job #1378659)

Utilizator sorynsooSorin Soo sorynsoo Data 6 martie 2015 13:31:42
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
stack<int> sx,sy;
vector<int> graf[100001];
set<int> rasp[100001];
set<int>::iterator it;
int n,m,x,y,i,j,k;
int nivel[100001],l[100001];
void extrage(int a, int b )
{
  int nod1,nod2;
  do
  {
    nod1=sx.top();   sx.pop();
    nod2=sy.top(); sy.pop();
    rasp[k].insert(nod1);
    rasp[k].insert(nod2);
  }while(nod1!=a && nod2!=b);
}
int df(int nod, int tata, int lvl)
{
    l[nod]=nivel[nod]=lvl;
    for(int i=0; i<graf[nod].size(); i++)
    {
        int next=graf[nod][i];
        if(next==tata)
            continue;
        if(!nivel[next])
        {
            //pun in stiva
            sx.push(nod); sy.push(next);
            df(next,nod,lvl+1);
            l[nod]=min(l[nod],l[next]);
            if(l[next]>=nivel[nod])
            {
                k++;
                extrage(nod,next);
            }
        }
        else
            l[nod]=min(l[nod],nivel[next]);
    }
}
int main()
{
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {
        cin>>x>>y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    df(1,0,1);
    cout<<k<<"\n";
    for(i=1; i<=k; i++)
    {
        for(it=rasp[i].begin(); it!=rasp[i].end(); it++)
            cout<<*it<<" ";
        cout<<"\n";
    }
}