Cod sursa(job #2416253)

Utilizator akaprosAna Kapros akapros Data 27 aprilie 2019 11:32:01
Problema Componente biconexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <bits/stdc++.h>
#define maxN 100002
#define maxM 200002

using namespace std;

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

int n, m;
vector < int > V[maxN];

int N, T, top;
struct Edge
{
    int u, v;
} st[maxM];
int inSt[maxN], low[maxN], disc[maxN], comp[maxN];

int nrC;
vector < int > C[maxM];

void AddEdge(int u, int v)
{
    V[u].push_back(v);
    V[v].push_back(u);
}
void AddEStack(int u, int v)
{
    ++ inSt[u];
    ++ inSt[v];
    st[++ top] = Edge{u, v};
}
void Bcc(Edge e)
{
    ++ nrC;
    while (top > 0)
    {
        Edge crt = st[top];
        -- top;
        if (comp[crt.u] != nrC)
        {
            comp[crt.u] = nrC;
            C[nrC].push_back(crt.u);
        }
        if (comp[crt.v] != nrC)
        {
            comp[crt.v] = nrC;
            C[nrC].push_back(crt.v);
        }
        -- inSt[crt.u];
        -- inSt[crt.v];
        if (crt.u == e.u && crt.v == e.v)
            break;
    }
}
void dfs(int u, int par)
{
    disc[u] = low[u] = ++ T;
    int nrC = 0;
    for (int v: V[u]) if (!disc[v]) ++ nrC;
    for (int v : V[u])
        if (!disc[v])
        {
            AddEStack(u, v);
            dfs(v, u);
            low[u] = min(low[v], low[u]);
            if ((low[v] >= disc[u] && disc[u] > 1) || (disc[u] == 1 && nrC > 1))
                Bcc(Edge{u, v});
        }
        else if (v != par && inSt[v])
        {
            low[u] = min(low[u], disc[v]);
            AddEStack(u, v);
        }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++ i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        -- u;
        -- v;
        AddEdge(u, v);
    }
    for (int i = 0; i < n; ++ i)
        if (!disc[i])
        {
            T = 0;
            dfs(i, -1);
        }
    printf("%d\n", nrC);
    for (int i = 1; i <= nrC; ++ i, printf("\n"))
        for (int it : C[i])
            printf("%d ", it + 1);
    return 0;
}