Cod sursa(job #2154223)

Utilizator AlexVulpoiuAlexandru Vulpoiu AlexVulpoiu Data 6 martie 2018 19:56:17
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
int n,m,i,j,c,t[100001],niv[100001],l[100001];
bool viz[100001];
vector <int> v[100001],st;
vector <int>::iterator it;
vector <int>::reverse_iterator rit;
void dfs(int k)
{
    st.push_back(k);
    for(it=v[k].begin();it!=v[k].end();it++)
        if(!viz[*it])
        {
            t[*it]=k;
            niv[*it]=niv[k]+1;
            dfs(*it);
        }
        else
            if(niv[*it]<l[k])
                l[k]=niv[*it];
}
int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d",&n,&m);
    while(m)
    {
        scanf("%d%d",&i,&j);
        v[i].push_back(j);
        v[j].push_back(i);
        m--;
    }
    for(i=1;i<=n;i++)
        l[i]=100001;
    dfs(1);
    for(i=1;i<=n;i++)
        if(l[i]>=niv[t[i]])
        {
            viz[i]=0;
            c++;
        }
    printf("%d\n",c);
    for(rit=st.rbegin();rit!=st.rend();rit++)
    {
        printf("%d ",*rit);
        if(!viz[*rit])
            printf("\n%d ",*rit);
    }
    return 0;
}