Cod sursa(job #1535194)

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

void pop(pair<int,int> x)
{
    int i;
    vector<int> tmp;
    rasp.push_back(tmp);
    freq.assign(cn+1, 0);
    while(st.top().first!=x.first||st.top().second!=x.second)
    {
        freq[st.top().first]=1;
        freq[st.top().second]=1;
        st.pop();
    }
    freq[st.top().first]=1;
    freq[st.top().second]=1;
    st.pop();
    for(i=1; i<=cn;i++)
        if(freq[i])
            rasp[last].push_back(i);
    last++;
}


void dfs(int u)
{
    int i,v;
    low[u]=time;
    disc[u]=time;
    time++;
    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++)
    {
        for(j=0; j<rasp[i].size(); j++)
            printf("%d ", rasp[i][j]);
        printf("\n");
    }
    return 0;
}