Cod sursa(job #1832688)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 20 decembrie 2016 18:51:57
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#define NODURI 100000
using namespace std;
vector <int>G[NODURI];
vector <int> sol[NODURI];
stack <pair<int,int> > st;
int counter;
int vViz[NODURI];
int m,n,vNivel[NODURI],vNivelDeAjuns[NODURI];
void citire()
{
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
}
void prinSol()
{
    printf("%d\n",counter);
    vector <int>::iterator x;
    for(int i=0; i<counter; i++)
    {
        for(x=sol[i].begin(); x!=sol[i].end(); x++)
            printf("%d ",*x);
        printf("\n");
    }
}

void DFS(int varf,int tata)
{
    vNivel[varf]=vNivel[tata]+1;
    vNivelDeAjuns[varf]=vNivel[varf];
    vViz[varf]=1;
    vector <int>::iterator it;
    for(it=G[varf].begin(); it!=G[varf].end(); it++)
    {
        if(*it!=tata)
        {
            if(!vViz[*it])
            {
                st.push(make_pair(varf,*it));
                DFS(*it,varf);
                vNivelDeAjuns[varf]=min(vNivelDeAjuns[varf],vNivelDeAjuns[*it]);
                if(vNivelDeAjuns[*it]>=vNivel[varf])
                {
                    while(*it!=st.top().second)
                    {
                        sol[counter].push_back(st.top().second);
                        st.pop();
                    }
                    sol[counter].push_back(st.top().second);
                    sol[counter].push_back(st.top().first);
                    st.pop();
                    counter++;
                }

            }
            else
            {
                vNivelDeAjuns[varf]=min(vNivelDeAjuns[varf],vNivel[*it]);
            }
        }
    }
}



int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    citire();
    for(int i=1;i<=n;i++)
        if(!vViz[i])
           DFS(i,0);
    prinSol();

    return 0;
}