Cod sursa(job #1706358)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 22 mai 2016 12:45:40
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

const int NMAX = 100000;
const int MMAX = 200000;

int dp[NMAX+5];
vector <int> v[NMAX+5];
int h[NMAX+5];
bool f[NMAX+5];
stack <int> st;

int NR;
vector <int> ans[MMAX+5];

void dfs(int nod)
{
    dp[nod] = h[nod];
    for(int i=0; i<v[nod].size(); i++)
    {
        if(h[v[nod][i]] == 0)
        {
            h[v[nod][i]] = h[nod]+1;
            dfs(v[nod][i]);
            dp[nod] = min(dp[nod], dp[v[nod][i]]);
        }
        else dp[nod] = min(dp[nod], h[v[nod][i]]);
    }
}

void biconex(int nod)
{
    for(int i=0; i<v[nod].size(); i++)
        if(!f[v[nod][i]])
        {
            st.push(v[nod][i]);
            f[v[nod][i]] = true;
            biconex(v[nod][i]);
            if(dp[v[nod][i]] >= h[nod])
            {
                while(st.top()!=nod)
                {
                    ans[NR].push_back(st.top());
                    st.pop();
                }
                ans[NR].push_back(nod);
                NR++;
            }
        }
}

int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=0; i<m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        x--;y--;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    h[0] = 1;
    dfs(0);
    f[0] = 1;
    st.push(0);
    biconex(0);
    printf("%d\n", NR);
    for(int i=0; i<NR; i++)
    {
        for(int j=0; j<ans[i].size(); j++)
            printf("%d ", ans[i][j]+1);
        printf("\n");
    }
    return 0;
}