Cod sursa(job #2198606)

Utilizator gabib97Gabriel Boroghina gabib97 Data 24 aprilie 2018 19:40:20
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>
#define N 100001

using namespace std;

int h[N], low[N];
vector<int> G[N];
vector<vector<int>> sol;
stack<pair<int, int>> edges;

void DFS(int s, int parent)
{
    low[s] = h[s];

    for (int &x : G[s])
        if (!h[x])
        {
            h[x] = h[s] + 1;
            edges.push(make_pair(s, x));
            DFS(x, s);

            low[s] = min(low[s], low[x]);
            if (low[x] >= h[s]) // s is a cut vertex
            {
                pair<int, int> p;
                vector<int> comp;
                do 
                {
                    p = edges.top();
                    edges.pop();
                    comp.push_back(p.second);
                } while (p.first != s || p.second != x);

                comp.push_back(s);
                sol.push_back(comp);
            }
        }
        else if (x != parent)
            low[s] = min(low[s], h[x]);
}

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

    int n, m, x, y;
    scanf("%i%i", &n, &m);

    while (m--)
    {
        scanf("%i%i", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }

    for (int i = 1; i <= n; i++)
        if (!h[i])
            h[i] = 1, DFS(i, 0);

    printf("%lu\n", sol.size());
    for (auto &v : sol)
    {
        for (int &x : v)
            printf("%i ", x);
        printf("\n");
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}