Cod sursa(job #669079)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 26 ianuarie 2012 01:17:47
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <vector>

using namespace std;

int a,b;
int dpt[100001],lp[100001];
stack <pair <int,int> > s;
vector <int> g[100001];
vector <vector <int> > c;

void cache_bc(int x,int y)
{
    vector <int> con;
    int tx,ty;

    do
    {
        tx=s.top().first;
        ty=s.top().second;
        s.pop();
        con.push_back(tx);
        con.push_back(ty);
    }
    while (tx!=x||ty!=y);

    c.push_back(con);
}

void dfs(int x,int f,int d)
{
    vector <int>::iterator it;

    dpt[x]=lp[x]=d;
    for (it=g[x].begin();it!=g[x].end();++it)
    {
        if (*it==f)
            continue;

        if (dpt[*it]==-1)
        {
            s.push(make_pair(x,*it));
            dfs(*it,x,d+1);
            lp[x]=min(lp[x],lp[*it]);

            if (lp[*it]>=dpt[x])
            {
                a=x;
                b=*it;
                cache_bc(x,*it);
            }
        }
        else
            lp[x]=min(lp[x],dpt[*it]);
    }
}

int main()
{
    int i,j,n,m,x,y;

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

    scanf("%d%d",&n,&m);
    for (;m>0;--m)
    {
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }

    memset(dpt,-1,sizeof(dpt));
    dfs(1, 0, 0);

    printf("%d\n",c.size());
    for (i=0;i<c.size();++i)
    {
        sort(c[i].begin(),c[i].end());
        c[i].erase(unique(c[i].begin(),c[i].end()),c[i].end());
        for (j=0;j<c[i].size();++j)
            printf("%d ",c[i][j]);
        printf("\n");
    }

    return 0;
}