Cod sursa(job #1528711)

Utilizator zertixMaradin Octavian zertix Data 19 noiembrie 2015 22:47:38
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.42 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;

vector < int > much;
vector < int > g[100005];
vector <int > rez[100005];

stack < pair < int ,int > > stk;

int n,m,x,y,nivel[100005],low[100005],nr,tx,ty;

void citesc()
{
    scanf("%d%d",&n,&m);

    for (int i=1; i<=m; ++i)
    {
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
}

void dfs(int nod,int tn,int number) ///tn->tatal nodului precedent->folosit pentru a nu folosi un vector de tati
                                    ///number retine nivelul actual->din aceleasi considerente
                                    ///nod=nod curent
{

    nivel[nod]=number;
    low[nod]=number;

    for (vector <int > :: iterator it=g[nod].begin(); it!=g[nod].end(); ++it)
    {
        if(*it ==tn)
            continue;

        if (nivel[*it]==-1)///daca nu e vizitat, adica daca sunt in arbore
        {
            stk.push(make_pair(nod,*it)); ///pun in stiva muchia
            dfs(*it,nod,number+1); ///apelez functia
            low[nod]=min(low[nod],low[*it]); ///vad daca nivelul accesibil lui it e cumva mai mic decat cel a lui nod
            if (nivel[nod]<=low[*it]) ///in cazul in care nivelul accesibil a lui *it e mai mare sau egal
                ///(adica chiar se termina in nod, atunci inseamna ca nod e NOD critic, adica am componenta biconexa
            {
                ++nr;
                do
                {
                    tx=stk.top().first;
                    ty=stk.top().second;
                    rez[nr].push_back(tx);
                    rez[nr].push_back(ty);
                    stk.pop();
                }
                while(tx!=nod || ty!=*it);
            }
        }
        else
            low[nod]=min(low[nod],nivel[*it]); ///sunt pe muchie inversa
    }

}


int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    citesc();
    for (int i=1;i<=n;++i)
        nivel[i]=-1;
    dfs(1,0,0);
    printf("%d\n",nr);
    for (int i=1;i<=nr;++i)
    {
        sort(rez[i].begin(),rez[i].end());
        rez[i].erase(unique(rez[i].begin(),rez[i].end()),rez[i].end());
        for (vector <int > :: iterator it=rez[i].begin(); it!=rez[i].end(); ++it)
            printf("%d ",*it);
        printf("\n");
    }
    return 0;
}