Cod sursa(job #2498482)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 23 noiembrie 2019 22:46:55
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#define u first
#define v second
using namespace std;
const int NMAX = 100000;
typedef pair <int , int> ii;
vector <int> G[NMAX + 5];
vector <vector <int> > comp;
stack <ii> st;
int dfn[NMAX + 5] , low[NMAX + 5] , nrcomp , ord;
void comp_biconexa(int u , int v)
{
    nrcomp ++;
    vector <int> s;
    ii aux;
    do
    {
        aux = st.top();
        st.pop();
        s.push_back(aux.v);
    }
    while(!st.empty() && aux.u != u && aux.v != v);
    s.push_back(aux.u);
    comp.push_back(s);
}
void dfs(int u , int tu)
{
    int v , j;
    ord ++;
    dfn[u] = low[u] = ord;
    for(j = 0 ; j < G[u].size() ; j ++)
    {
        v = G[u][j];
        if(v != tu && dfn[v] < dfn[u])
            if(dfn[v] == -1)
            {
                st.push(make_pair(u , v));
                dfs(v , u);
                low[u] = min(low[u] , low[v]);
                if(low[v] >= dfn[u])
                    comp_biconexa(u , v);
            }
            else if(v != tu)
                low[u] = min(low[u] , dfn[v]);
    }
}
int main()
{
    freopen("biconex.in" , "r" , stdin);
    freopen("biconex.out" , "w" , stdout);
    int n , m , u , v , i , j;
    scanf("%d%d" , &n , &m);
    for(i = 1 ; i <= m ; i ++)
    {
        scanf("%d%d" , &u , &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(i = 1 ; i <= n ; i ++)
        dfn[i] = low[i] = -1;
    st.push(make_pair(-1 , 1));
    for(i = 1 ; i <= n ; i ++)
        if(dfn[i] == -1)
        {
            ord = 0;
            dfs(i , -1);
        }
    printf("%d\n" , nrcomp);
    for(i = 0 ; i < comp.size() ; i ++)
    {
        for(j = 0 ; j < comp[i].size() ; j ++)
            printf("%d " , comp[i][j]);
        printf("\n");
    }
    return 0;
}