Cod sursa(job #1883658)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 18 februarie 2017 09:52:53
Problema Componente biconexe Scor 42
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int st[100001];
int lst = 0;
vector< vector<int> > rez;
vector<int> g[100001];
int viz[100001], low[100001];
int n, m;

void dfs(int nod, int tnod)
{
    viz[nod] = viz[tnod] + 1;
    low[nod] = viz[nod];
    st[lst++] = nod;
    for(int i = 0; i < g[nod].size(); i++)
    {
        if(g[nod][i] != tnod)
        {
            if(!viz[g[nod][i]])
            {
                dfs(g[nod][i], nod);
                low[nod] = min(low[nod], low[g[nod][i]]);

                if(viz[nod] <= low[g[nod][i]])
                {
                    vector<int> r;
                    while(st[lst - 1] != nod)
                    {
                        lst--;
                        r.push_back(st[lst]);
                    }
                    r.push_back(st[lst - 1]);
                    sort(r.begin(), r.end());
                    rez.push_back(r);
                }
            }
            else low[nod] = min(low[nod], low[g[nod][i]]);
        }
    }
}

int main()
{
    int a, b;
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    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);
    }
    viz[0] = 1;
    low[0] = 1;
    dfs(1, 0);
    printf("%d\n", rez.size());
    for(int i = 0; i < rez.size(); i++)
    {
        for(int j = 0; j < rez[i].size(); j++)
        {
            printf("%d ", rez[i][j]);
        }
        printf("\n");
    }
    return 0;
}