Cod sursa(job #1959642)

Utilizator antanaAntonia Boca antana Data 9 aprilie 2017 19:04:09
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <bits/stdc++.h>

#define MAXN 100001

using namespace std;

vector <int> G[MAXN], answer[MAXN];
stack < pair<int, int> > stk;

int n, m, root, biconex, depth[MAXN], low[MAXN], father[MAXN];
bool seen[MAXN];

inline void createComponent(int node1, int node2) {
    biconex++;
    while(stk.top().first != node1 && stk.top().second != node2) {
        answer[biconex].push_back(stk.top().second);
        stk.pop();
    }
    answer[biconex].push_back(stk.top().second);
    answer[biconex].push_back(stk.top().first);
    stk.pop();
}

void dfs(int node) {
    seen[node] = 1;
    low[node] = depth[node];
    for(int son: G[node]) {
        if(!seen[son]) {
            depth[son] = depth[node] + 1;
            father[son] = node;
            stk.push({node, son});
            dfs(son);
            low[node] = min(low[node], low[son]);
            if(low[son] >= depth[node])
                createComponent(node, son);
        }else if(son != father[node])
                low[node] = min(low[node], depth[son]);
    }
}

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

    int i, x, y;

    scanf("%d%d", &n, &m);

    for(i=1; i<=m; ++i) {
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }

    depth[1] = 1;
    dfs(1);

    printf("%d\n", biconex);
    for(i=1; i<=biconex; ++i) {
        for(int node: answer[i])
            printf("%d ", node);
        printf("\n");
    }

    return 0;
}