Cod sursa(job #2065101)

Utilizator vladdy47Bucur Vlad Andrei vladdy47 Data 13 noiembrie 2017 13:13:21
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
# include <bits/stdc++.h>

using namespace std;

const int nmax = 2 * 1e5 + 5;

vector <int> ans[nmax], G[nmax];
stack < pair <int, int> > st;
bool selected[nmax];
int low[nmax], lvl[nmax], n, m, i, N;

void biconex(pair <int, int> x)
{
    ++N;
    while (!st.empty())
    {
        pair <int, int> y = st.top();
        ans[N].push_back(y.second);
        st.pop();
        if (y == x) break;
    }
    ans[N].push_back(x.first);
}

void dfs(int node)
{
    selected[node] = true;
    low[node] = lvl[node];

    for (auto &it: G[node])
        if (!selected[it])
        {
            lvl[it] = lvl[node] + 1;

            st.push({node, it});

            dfs(it);

            if (lvl[node] <= low[it]) biconex({node, it});

            low[node] = min(low[node], low[it]);
        }
        else low[node] = min(low[node], lvl[it]);

}

int main ()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);

    scanf("%d %d\n", &n, &m);

    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        scanf("%d %d\n", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }

    dfs(1);

    printf("%d\n", N);

    for (i = 1; i <= N; ++i)
    {
        for (auto &it: ans[i])
            printf("%d ", it);

        printf("\n");
    }

    return 0;
}