Cod sursa(job #1783655)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 19 octombrie 2016 12:13:20
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e5+5;

int low[Nmax], level[Nmax], n, m, i, x, y;
stack< pair<int,int> > st;
vector< vector<int> > ans;
vector<int> v[Nmax];

void get_comp(int node)
{
    ans.push_back(vector<int> ());
    pair<int,int> el;

    do
    {
        el = st.top();
        st.pop();

        ans.back().push_back(el.second);
    }
    while(el.first!=node);

    ans.back().push_back(node);
}

void dfs(int node)
{
    for(auto son : v[node])
    if(!level[son])
    {
        st.push({ node,son });
        level[son] = low[son] = level[node]+1;
        dfs(son);
        low[node] = min(low[node], low[son]);

        if(low[son]>=level[node])
            get_comp(node);
    }
    else if(level[son]!=level[node]-1)
        low[node] = min(low[node], level[son]);
}

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

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

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

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

    printf("%d\n", ans.size());

    for(auto comp : ans)
    {
        for(auto x : comp) printf("%d ", x);
        printf("\n");
    }

    return 0;
}