Cod sursa(job #1345291)

Utilizator alecsandrualex cuturela alecsandru Data 17 februarie 2015 15:14:25
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

const int MAXN = 100000;

int h[MAXN + 1];
int ret[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++;
}
void dfs(int tata,int last)
{
    int fiu,i,temp,cr=0;
    h[tata]=h[last]+1;
    ret[tata]=h[tata];
    viz[tata]=1;
    st[++top]=tata;
    for(i=0;i<drum[tata].size();i++)
    {
        fiu=drum[tata][i];
        if(fiu!=last)
        {
            if(viz[fiu]==0)
            {
                cr++;
                if(cr>1)
                    st[++top]=tata;
                dfs(fiu,tata);
                if(ret[fiu]>=h[tata] && last!=0)
                {
                    nod_art.push_back(tata);
                    rezolva(tata);
                }
                ret[tata]=min(ret[tata],ret[fiu]);
            }
            else
            {
                ret[tata]=min(ret[tata],h[fiu]);
            }
        }
    }
    if(cr>1 && last==0)
    {
        nod_art.push_back(tata);
        rezolva(tata);
    }
}
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);
    }
    h[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());
        rez[i].resize(unique(rez[i].begin(),rez[i].end()) - rez[i].begin());
        for(j=0;j<rez[i].size();j++)
            printf("%d ",rez[i][j]);
        printf("\n");
    }
    return 0;
}