Cod sursa(job #2907708)

Utilizator mateicosCostescu Matei mateicos Data 31 mai 2022 11:49:48
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
# include <cstdio>
# include <vector>

using namespace std;

# define min(a, b) (a < b ? a : b)
# define MAXN 100005

int N, M, i, cnt, comp;
int s[MAXN];
int Up[MAXN];
int Lvl[MAXN];
vector <int> E;
vector <int> G[MAXN];
vector <int> C[MAXN];

void find_Cb(int nod, int pap, int niv)
{
    vector <int> :: iterator it;

    Lvl[nod] = Up[nod] = niv;
    for (it = G[nod].begin(); it < G[nod].end(); ++it)
    {

        if (*it == pap) continue;
        if (!Lvl[*it])
        {
            E.push_back(nod);
            E.push_back(*it);

            find_Cb(*it, nod, niv + 1);

            Up[nod] = min(Up[nod], Up[*it]);

            if (Up[*it] >= Lvl[nod])
            {
                int x = 0, y;

                ++comp;
                do
                {
                    y = x;
                    x = *(E.end() - 1);
                    E.pop_back();

                    if (s[x] != comp) C[comp].push_back(x);
                    s[x] = comp;
                }
                while (x != nod || y != *it);
            }
        }
        else Up[nod] = min(Up[nod], Lvl[*it]);
    }
}

void print()
{
    int i;
    vector <int> :: iterator it;


    printf("%d\n",comp);
    for (i = 1; i <= comp; ++i)
    {
        for (it = C[i].begin(); it != C[i].end(); ++it)
            printf("%d ",*it);
        printf("\n");
    }
}

int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d %d",&N, &M);
    for (i = 1; i <= M; ++i)
    {
        int x, y;
        scanf("%d %d",&x, &y);

        G[x].push_back(y);
        G[y].push_back(x);
    }
    cnt = comp = 0;
    find_Cb(1, 0, 1);
    print();
    return 0;
}