Cod sursa(job #2188802)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 27 martie 2018 14:44:22
Problema Componente biconexe Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <bits/stdc++.h>

using namespace std;

int lrez;
vector<int> rez[100005];
vector<int> g[100005];
int low[100005];
int viz[100005];
int st[100005];
int lst;

void dfs(int nod, int t)
{
    viz[nod] = viz[t] + 1;
    low[nod] = viz[nod];
    st[lst++] = nod;
    for(int i = 0; i < g[nod].size(); i++)
    {
        if(g[nod][i] != t)
        {
            if(viz[g[nod][i]] == 0)
            {
                dfs(g[nod][i], nod);
                low[nod] = min(low[nod], low[g[nod][i]]);
                if(low[g[nod][i]] >= viz[nod])
                {
                    while(lst > 0 && (st[lst - 1] != g[nod][i] || st[lst - 2] != nod))
                    {
                        rez[lrez].push_back(st[lst - 1]);
                        lst--;
                    }
                    lst--;
                    rez[lrez].push_back(nod);
                    rez[lrez].push_back(g[nod][i]);
                    lrez++;
                }
            }
            else low[nod] = min(low[nod], viz[g[nod][i]]);
        }
    }
}

int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    int n, m, a, b;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d", &a, &b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i = 1; i <= n; i++)
    {
        if(viz[i] == 0)
        {
            lst = 0;
            dfs(i, 0);
        }
    }
    printf("%d\n", lrez);
    for(int i = 0; i < lrez; i++)
    {
        sort(rez[i].begin(), rez[i].end());
        for(int j = 0; j < rez[i].size(); j++)
            printf("%d ", rez[i][j]);
        printf("\n");
    }
    return 0;
}