Cod sursa(job #1969147)

Utilizator ZeBuGgErCasapu Andreas ZeBuGgEr Data 18 aprilie 2017 12:06:21
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
#include<cstdio>
#include<vector>

using namespace std;

const int NMAX = 100000;

int n,m;
vector<int> adj[1 + NMAX];
int niv[1 + NMAX], niv_min[1 + NMAX];
int stk[1 + 2 * NMAX];
int top;
vector<int> res[1 + NMAX];
int res_ct;

int mi(int a, int b)
{
    if(a < b)
    {
        return a;
    }
    return b;
}

void solve(int nod, int lvl, int tata)
{
    top++;
    stk[top] = nod;

    niv[nod] = lvl;
    niv_min[nod] = lvl;
    bool flag = 0;

    int next;
    int sz = adj[nod].size();
    for(int i = 0; i < sz; i++)
    {
        next = adj[nod][i];
        if(next != tata)
        {
            if(niv[next] == 0)
            {
                solve(next, lvl + 1, nod);

                niv_min[nod] = mi(niv_min[nod], niv_min[next]);

                if(niv[nod] <= niv_min[next])
                {
                    res_ct++;
                    while(stk[top] != next)
                    {
                        res[res_ct].push_back(stk[top]);
                        top--;
                    }
                    res[res_ct].push_back(stk[top]);
                    top--;

                    res[res_ct].push_back(nod);
                }
            }
            else
            {
                niv_min[nod] = mi(niv_min[nod], niv[next]);
            }

        }
    }
}

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

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

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

    solve(1, 1, 0);

    printf("%d\n", res_ct);
    for(int i = 1; i <= res_ct; i++)
    {
        while(!res[i].empty())
        {
            printf("%d ", res[i].back());
            res[i].pop_back();
        }
        printf("\n");
    }
}