Cod sursa(job #1520788)

Utilizator tudormaximTudor Maxim tudormaxim Data 9 noiembrie 2015 14:45:42
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>
using namespace std;
const int nmax = 100005;
vector <int> g[nmax], comp[nmax], v;
stack <pair<int,int> > st;
int low[nmax], lev[nmax], tata[nmax], sol;
bool viz[nmax];

void get_sol(int x, int y)
{
    int a, b;
    sol++;
    do
    {
        a=st.top().first;
        b=st.top().second;
        comp[sol].push_back(b);
        st.pop();
    } while(a!=x || b!=y);
    comp[sol].push_back(a);
}

void dfs(int dad)
{
    int i, son;
    viz[dad]=true;
    low[dad]=lev[dad];
    for(i=0; i<g[dad].size(); i++)
    {
        son=g[dad][i];
        if(!viz[son])
        {
            lev[son]=lev[dad]+1;
            st.push(make_pair(dad, son));
            dfs(son);
            low[dad]=min(low[dad], low[son]);
            if(low[son] >= lev[dad]) /// dad este nod critic
                get_sol(dad, son);
        }
        else low[dad]=min(low[dad], lev[son]);
    }
}

int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    int n, m, x, y, i, j;
    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);
    }

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

    printf("%d\n", sol);
    for(i=1; i<=sol; i++)
    {
        sort(comp[i].begin(), comp[i].end());
        for(j=0; j<comp[i].size(); j++)
            printf("%d ", comp[i][j]);
        printf("\n");
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}