Cod sursa(job #2154588)

Utilizator AlexVulpoiuAlexandru Vulpoiu AlexVulpoiu Data 7 martie 2018 09:12:51
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 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> st,v[100001];
vector <int>::reverse_iterator rit;
void dfs(int k)
{
    int it;
    st.push_back(k);
    viz[k]=1;
    for(it=0;it!=v[k].size();it++)
        if(!viz[v[k][it]])
        {
            t[v[k][it]]=k;
            niv[v[k][it]]=niv[k]+1;
            dfs(v[k][it]);
        }
        else
            if(niv[v[k][it]]<l[k])
                l[k]=niv[v[k][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;
    l[1]=0;
    dfs(1);
    c=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);
    }
    printf("\n");
    return 0;
}