Cod sursa(job #1908340)

Utilizator gabib97Gabriel Boroghina gabib97 Data 7 martie 2017 00:47:32
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <stdio.h>
#include <vector>
#include <stack>

#define N 100005
using namespace std;
int n, m, h[N], u[N], nr, t[N];
bool o[N];
vector<int> G[N], C[N];
stack<pair<int, int> > S;

void DFS(int s) {
    pair<int, int> p;
    u[s] = h[s];
    o[s] = 1;
    for (auto x:G[s])
        if (!o[x]) {
            S.push(make_pair(s, x));
            h[x] = h[s] + 1;
            t[x] = s;
            DFS(x);
            u[s] = min(u[s], u[x]);
            if (u[x] >= h[s]) //s - punct critic
            {
                nr++;
                do {
                    p = S.top();
                    S.pop();
                    C[nr].push_back(p.second);
                } while (p.first != s || p.second != x);
                C[nr].push_back(s);
            }
        } else if (x != t[s])
            u[s] = min(u[s], h[x]);
}

int main() {
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    int x, y, i;
    scanf("%i%i", &n, &m);
    for (i = 1; i <= m; i++) {
        scanf("%i%i", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for (i = 1; i <= n; i++)
        if (!o[i]) DFS(1);
    printf("%i\n", nr);
    while (nr--) {
        for (auto x:C[nr + 1])
            printf("%i ", x);
        printf("\n");
    }
    return 0;
}