Cod sursa(job #1966509)

Utilizator mariakKapros Maria mariak Data 15 aprilie 2017 12:32:17
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <bits/stdc++.h>
#define pii pair <int, int>
#define mp make_pair
#define maxN 100002

FILE *fin  = freopen("biconex.in", "r", stdin);
FILE *fout = freopen("biconex.out", "w", stdout);

using namespace std;
int N, M;
vector <int> G[maxN];
bitset <maxN> used;
stack <pii> st;
vector <int> aux;
vector < vector<int> >bcc;
int parent[maxN], disc[maxN], low[maxN], t;

void build_BCC(pii p){
    pii edge;
    do{
        edge = st.top();
        st.pop();
        aux.push_back(edge.first);
        aux.push_back(edge.second);
    }while(edge != p);
    sort(aux.begin(), aux.end());
    aux.erase(unique(aux.begin(), aux.end()), aux.end());
    bcc.push_back(aux);
    aux.clear();
}

void dfs(int node){
    low[node] = disc[node] = ++t;
    for(int son : G[node])
        if(!disc[son]){
            parent[son] = node;
            st.push(mp(node, son));
            dfs(son);
            low[node] = min(low[node], low[son]);
            if(low[son] >= disc[node]) // find a BCC
                build_BCC(mp(node, son));
        }
        else if(son != parent[node] && disc[son] < low[node]){
            low[node] = disc[son]; // just one back edge
            st.push(mp(node, son));
        }
}

int main(){
    scanf("%d %d", &N, &M);
    for(int i = 1; i <= M; ++ i){
        int x, y;
        scanf("%d %d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1);
    printf("%d\n", (int)bcc.size());
    for(auto comp : bcc){
        for(auto node : comp)
            printf("%d ", node);
        printf("\n");
    }
    return 0;
}