Cod sursa(job #1097767)

Utilizator Juve45UAIC Alexandru Ionita Juve45 Data 3 februarie 2014 22:01:21
Problema Componente biconexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

#define pb push_back
#define dmax 1234
#define x first
#define y second


int n, m, dfn[dmax], l[dmax], nr, c, start, nrs, con[dmax];
vector              <int > v[dmax];
typedef             pair <int, int> dp;
vector <dp> st;
vector <int > v2[dmax];

void print_biconex(int a, int b)
{
    c++;
dp as=make_pair(a, b);
dp is=make_pair(b, a);
for(int i=st.size()-1;i>=0;i--)
{
    if(con[st[i].x]!=c)
    {
        con[st[i].x]=c;
        v2[c].pb(st[i].x);
    }
    if(con[st[i].y]!=c)
    {
        con[st[i].y]=c;
        v2[c].pb(st[i].y);
            }
st.pop_back();
if(as==st[i] || is==st[i])
    break;

}

}


void DFS(int k, int kk)
{
    nr++;
    dfn[k]=nr;
    l[k]=nr;

    for(int i=0; i<v[k].size(); i++)
    {
        int a=v[k][i];
        if(a!=kk && dfn[a]<dfn[k])
        {
            dp asd;
            asd.x=a;
            asd.y=k;
            st.pb(asd);
            }
        if(dfn[a]==0)
        {
            DFS(a, k);
            l[k]=min(l[a], l[k]);


            if(l[a]>=dfn[k]) {
                    //printf("muchia: %i %i cu bic:", k, a);
                print_biconex(k, a);
            }

        }
        else
        {
            if(a!=kk)
                l[k]=min(l[k], dfn[a]);

        }

    }


}


void read()
{
    int a, b;
    scanf("%i%i", &n, &m);
    for(int i=1; i<=m; i++)
    {
        scanf("%i%i", &a, &b);
        {
            v[a].pb(b);
            v[b].pb(a);
        }
    }
}


int main()
{

    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    read();
    start=1;
    DFS(start, -1);
    //print_biconex(1,2);
    printf("%i\n", c);
    for(int i=1;i<=c;i++)
    {
        for(int j=0;j<v2[i].size();j++)
        printf("%i ", v2[i][j]);
        printf("\n");
    }
    return 0;
}