Cod sursa(job #1923460)

Utilizator PaulCbnCiobanu Paul PaulCbn Data 11 martie 2017 01:36:22
Problema Componente biconexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>

#define NMAX 100005
#define MMAX 200005

using namespace std;

int N,M;
vector<int> graf[NMAX];
int sus[NMAX],niv[NMAX];

void citire()
{
    scanf("%d%d",&N,&M);
    for(int i=1; i<=M; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        graf[x].push_back(y);
    }
}

stack<pair<int,int> > stiva;
vector<int> rez[NMAX];
int k;
void elim(int nod)
{
    k++;
    while(stiva.top().second != nod)
    {
        rez[k].push_back(stiva.top().second);
        stiva.pop();
    }
    rez[k].push_back(stiva.top().second);
    rez[k].push_back(stiva.top().first);
    stiva.pop();
}

void dfs(int nod,int t)
{
    niv[nod]=niv[t]+1;
    sus[nod]=niv[nod];

    for(vector<int>::iterator ii = graf[nod].begin(); ii!=graf[nod].end(); ii++)
        if(t==*ii)
            continue;
        else if(niv[*ii] == 0)
        {
            stiva.push(make_pair(nod,*ii));
            dfs(*ii,nod);
            sus[nod]=min(sus[nod],sus[*ii]);

            if(niv[nod] <= sus[*ii])///punct de articulatie
                elim(*ii);
        }
        else
            sus[nod] = min(sus[nod],niv[*ii]);


}

void afisare()
{
    printf("%d\n",k);
    for(int i=1; i<=k; i++)
    {
        for(vector<int>::iterator ii = rez[i].begin(); ii!=rez[i].end(); ii++)
            printf("%d ",*ii);
        printf("\n");
    }
}

int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout );
    citire();
    dfs(1,0);
    afisare();
    return 0;
}