Cod sursa(job #1344096)

Utilizator alecsandrualex cuturela alecsandru Data 16 februarie 2015 12:54:06
Problema Componente biconexe Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

const int MAXN = 100000;

int grad[MAXN + 1];
bool viz[MAXN + 1];
vector <int> drum[MAXN + 1],nod_art,rez[MAXN + 1];
int top,st[MAXN + 1000];
int n,m,cnt;

void rezolva(int stop)
{
    int temp;
    while(st[top] != stop && top != 0)
    {
        temp=st[top];
        rez[cnt].push_back(temp);
        top--;
    }
    rez[cnt].push_back(stop);
    cnt++;
}
int dfs(int tata,int last)
{
    int fiu,i,temp,ret=grad[tata];
    viz[tata]=1;
    st[++top]=tata;
    if(drum[tata].size()==1)
        ret=grad[last];
    else
    {
        for(i=0;i<drum[tata].size();i++)
        {
            fiu=drum[tata][i];
            if(fiu!=last)
            {
                if(viz[fiu]==0)
                {
                    grad[fiu]=grad[tata]+1;
                    temp=dfs(fiu,tata);
                    if(temp==grad[tata])
                    {
                        nod_art.push_back(tata);
                        rezolva(tata);
                    }
                    ret=min(ret,temp);
                }
                else
                {
                    ret=min(ret,grad[fiu]);
                }
            }
        }
    }
    return ret;
}
int main()
{
    int i,j,x,y;
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        drum[x].push_back(y);
        drum[y].push_back(x);
    }
    grad[1]=1;
    dfs(1,0);
    if(top!=0)
        rezolva(1);
    printf("%d\n",cnt);
    for(i=0;i<cnt;i++)
    {
        sort(rez[i].begin() , rez[i].end());
        for(j=0;j<rez[i].size();j++)
            printf("%d ",rez[i][j]);
        printf("\n");
    }
    return 0;
}