Cod sursa(job #1169415)

Utilizator cioionutFMI Ionut Ciocoiu cioionut Data 11 aprilie 2014 04:56:03
Problema Componente biconexe Scor 28
Compilator cpp Status done
Runda Arhiva educationala Marime 2.06 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;

void dfs(int x,vector <int> a[],vector <int> b[],vector <int> &viz,int **&d,int &it,vector <int> &vizz)
{
    //cout<<x<<" ";
    viz[x]=1;int i;
    for(i=0;i<a[x].size();i++)
        if (!viz[a[x][i]])
            {   d[0][a[x][i]]=d[1][a[x][i]]=d[0][x]+1;

                //cout<<x<<" "<<a[x][i]<<"\n";
                dfs(a[x][i],a,b,viz,d,it,vizz);
                //cout<<x<<"-"<<d[1][x]<<" "<<a[x][i]<<"-"<<d[1][a[x][i]]<<"\n";
                if(d[1][x]>d[1][a[x][i]]) d[1][x]=d[1][a[x][i]];

                //cout<<x<<" "<<a[x][i]<<"\n";
                if (!vizz[a[x][i]]) {viz[a[x][i]]=1;b[it].push_back(a[x][i]);}
                if (!vizz[x]) {viz[x]=1;b[it].push_back(x);}
                if(d[0][x]<=d[1][a[x][i]]) {it++;for(int h=0;h<vizz.size();h++) vizz[h]=0;}//cout<<x<<"\n";}

            }
        else if(abs(d[0][a[x][i]]-d[0][x])!=1)
                    {       if(d[0][a[x][i]]<d[0][x]&&d[0][a[x][i]]<d[1][x])  d[1][x]=d[0][a[x][i]];
                                else d[1][a[x][i]]=d[0][x];
                        }
}
int main()
{
    ifstream f("biconex.in");
    ofstream g("biconex.out");
    int n,m,i,j,it=1;
    f>>n>>m;
    vector <int> a[n+1];
    vector <int> b[n+1];
    vector <int> viz(n+1,0);
    int **d;
    d=new int *[2];
    d[0]=new int[n+1];
    d[1]=new int[n+1];
    for(i=1;i<=n;i++) d[0][i]=d[1][i]=0;
    for(i=0;i<m;i++)
    {   int x,y;f>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    vector <int> vizz(n+1,0);
    d[0][1]=d[1][1]=1;
    dfs(1,a,b,viz,d,it,vizz);
    //if(it-1==1)
    g<<it-1;
    for(i=1;i<it;i++) {g<<'\n';
        for(j=b[i].size()-1;j>=0;j--) g<<b[i][j]<<" ";}

/*
    for(i=1;i<=n;i++) cout<<i<<": "<<d[0][i]<<" "<<d[1][i]<<"\n";
    cout<<'\n';
        for(i=1;i<=n;i++)
        {
        cout<<i<<":";
        for(j=0;j<a[i].size();j++) cout<<a[i][j]<<" ";
        cout<<'\n';
        }
*/
    f.close();
    return 0;
}