Cod sursa(job #1960324)

Utilizator akaprosAna Kapros akapros Data 10 aprilie 2017 12:59:55
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include <bits/stdc++.h>
#define maxN 100005
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 t, disc[maxN], low[maxN], parent[maxN];
int used[maxN];
struct Edge
{
    int x, y;
} St[2 * maxN];
/* =============== */
int ans, nrE;
vector < int > BCC[2 * maxN];

void bcc(int x, int y)
{
    Edge e;
    ++ ans;
    do
    {
        e = St[nrE --];
        if (used[e.x] != ans)
        {
            BCC[ans].push_back(e.x);
            used[e.x] = ans;
        }
        if (used[e.y] != ans)
        {
            BCC[ans].push_back(e.y);
            used[e.y] = ans;
        }
        if (e.x == x && e.y == y)
            break;

    }
    while (nrE > 0);
}

void dfs(int u)
{
    int nrCh = 0;
    disc[u] = low[u] = ++ t;
    for (int v : V[u])
        if (!disc[v])
            ++ nrCh;
    for (int v : V[u])
        if (!disc[v])
        {
            St[++ nrE] = {u, v};
            parent[v] = u;
            dfs(v);
            low[u] = min(low[u], low[v]);
            if ((disc[u] == 1 && nrCh > 1) ||
                    (disc[u] > 1 && low[v] >= disc[u])) /// check if u is an articulation point
                bcc(u, v);
        }
        else if (v != parent[u] && low[u] > disc[v])
        {
            low[u] = disc[v];
            //St[++ nrE] = {u, v};
        }
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++ i)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        V[x].push_back(y);
        V[y].push_back(x);
    }
    for (int i = 1; i <= n; ++ i)
        if (!disc[i])
        {
            nrE = 0;
            t = 0;
            dfs(i);
        }
    printf("%d\n", ans);
    for (int i = 1; i <= ans; ++ i)
    {
        sort(BCC[i].begin(), BCC[i].end());
        int l = BCC[i].size();
        for (int j = 0; j < l; ++ j)
            printf("%d ", BCC[i][j]);
        printf("\n");
    }
    return 0;
}