Cod sursa(job #2189502)

Utilizator aIexpetrescuPetrescu Alexandru aIexpetrescu Data 28 martie 2018 15:13:29
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 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])
                    {
                        rez[lrez].push_back(st[lst - 1]);
                        lst--;
                    }
                    rez[lrez].push_back(st[lst - 1]);
                    lst--;
                    rez[lrez].push_back(nod);
                    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)
            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");
    }
   /* printf("\n\n\n\n\n-----------\n");
    for(int i = 1; i <= n; i++)
        printf("%d ", low[i]);*/
    return 0;
}