Cod sursa(job #2376513)

Utilizator akaprosAna Kapros akapros Data 8 martie 2019 16:05:08
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <bits/stdc++.h>
#define maxN 100002
#define pii pair <int, int>
#define f first
#define s second
using namespace std;

FILE *fin = freopen("biconex.in", "r", stdin);
FILE *fout = freopen("biconex.out", "w", stdout);

int n, m;
vector < int > G[maxN];
static int t = 0;

int disc[maxN], low[maxN], comp[maxN];
pii st[maxN];
int top;

int ans;
vector < int > C[maxN];

void bcc(int u, int v)
{
    ++ ans;
    comp[u] = comp[v] = ans;
    C[ans - 1].push_back(u);
    C[ans - 1].push_back(v);
    while (top > 0 && (st[top].f != u || st[top].s != v))
    {
        int nod = st[top].f;
        if (comp[nod] != ans)
        {
            comp[nod] = ans;
            C[ans - 1].push_back(nod);
        }
        nod = st[top].s;
        if (comp[nod] != ans)
        {
            comp[nod] = ans;
            C[ans - 1].push_back(nod);
        }
        -- top;
    }
    -- top;
}
void dfs(int u, int par)
{
    int nrCh = 0;
    disc[u] = low[u] = ++ t;
    for (int v : G[u])
        if (!disc[v])
            ++ nrCh;
    for (int v : G[u])
        if (!disc[v])
        {
            ++ nrCh;
            st[++ top] = pii{u, v};
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if ((disc[u] > 1 && low[v] >= disc[u]) || (disc[u] == 1 && nrCh > 1))
                bcc(u, v);
        }
        else if (v != par && low[u] > disc[v])
        {
            low[u] = disc[v];
            st[++ top] = pii{u, v};
        }
}
int main()
{
    scanf("%d%d", &n, &m);

    while (m --)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; ++ i)
        if (!disc[i])
        {
            t = 0;
            dfs(i, -1);
        }

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

    for (int i = 0; i < ans; ++ i, printf("\n"))
        for (int u : C[i])
            printf("%d ", u);
    return 0;
}