Cod sursa(job #1535462)

Utilizator vazanIonescu Victor Razvan vazan Data 24 noiembrie 2015 19:43:12
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
#define NMAX 100000
vector<int> G[NMAX+10], dad, low, disc;
vector<vector<int> > rasp;
stack<pair<int, int> > st;
int cr, tm=1, last=0, cn;

void pop(pair<int,int> x)
{
    pair<int,int> debug;
    vector<int> tmp;
    rasp.push_back(tmp);
    while(st.top().first!=x.first||st.top().second!=x.second)
    {
        rasp[last].push_back(st.top().first);
        rasp[last].push_back(st.top().second);
        st.pop();
    }
    rasp[last].push_back(st.top().first);
    rasp[last].push_back(st.top().second);
    st.pop();
    last++;
}


void dfs(int u)
{
    int i,v;
    low[u]=tm;
    disc[u]=tm;
    tm++;
    for(i=0;i<G[u].size(); i++)
    {
        v=G[u][i];
        if(!disc[v])
        {
            st.push(make_pair(u, v));
            dad[v]=u;
            dfs(v);
            if(low[v]<low[u])
                low[u]=low[v];
            if(low[v]>=disc[u])
                pop(make_pair(u,v));
        }
        else if(v!=dad[u])
            low[u]=min(low[u], disc[v]);

    }
}


int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out","w", stdout);
    int n, m, u, v, i;
    scanf("%d%d", &n, &m);
    cn=n;
    for(i=1; i<=m; i++)
    {
        scanf("%d%d", &u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dad.assign(n+1, 0);
    low.assign(n+1, 0);
    disc.assign(n+1, 0);
    dfs(1);
    printf("%d\n", last);
    int j;
    for(i=0; i<last; i++)
    {
        sort(rasp[i].begin(), rasp[i].end());
        printf("%d ", rasp[i][0]);
        for(j=1; j<rasp[i].size(); j++)
            if(rasp[i][j]!=rasp[i][j-1])
                printf("%d ", rasp[i][j]);
        printf("\n");
    }
    return 0;
}