Cod sursa(job #2174405)

Utilizator ionutpop118Pop Ioan Cristian ionutpop118 Data 16 martie 2018 11:53:30
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
const int NMAX = 100000;
struct muchie
{
    int x, y;
}; stack <muchie> st; muchie aux;
vector <int> g[NMAX + 5], sol[NMAX + 5];
int t[NMAX + 5], niv[NMAX + 5], low[NMAX + 5], nivel, nr;
void solve(int a, int b)
{
    int x, y; ++nr;
    do {
        x = st.top().x ; y = st.top().y;
        st.pop(); sol[nr].push_back(y);
    } while (x != a && y != b);
    sol[nr].push_back(x);
}
void dfs(int x)
{
    int y; ++nivel;
    niv[x] = low[x] = nivel;
    for (int i = 0; i < g[x].size(); ++i)
    {
        y = g[x][i];
        if (y != t[x])
            if (niv[y] == 0)
            {
                aux.x = x; aux.y = y; st.push(aux);
                t[y] = x; dfs(y);
                if (low[y] >= niv[x]) 
                    solve(x, y);
                low[x] = min(low[x], low[y]);
            }
            else
               low[x] = min(low[x], niv[y]); 
    }
}
int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    int n, m, x, y;
    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);
    }
    
    for (int i = 1; i <= n; ++i)
        if (niv[i] == 0)
            dfs(i);
    
    printf("%d\n", nr);
    for (int i = 1; i <= nr; ++i)
    {
        for (int j = 0; j < sol[i].size(); ++j)
            printf("%d ", sol[i][j]);
        printf("\n");
    }
    return 0;
}