Cod sursa(job #1028449)

Utilizator StickmanLazar Alexandru Stickman Data 14 noiembrie 2013 09:21:28
Problema Componente biconexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

vector <int> v[100001];
int n,m,cost[100001],t[100001],pc[200001],po[200001],k,afis[100001],nr,mat[500][10001],nivel[100001];
ofstream out("biconex.out");
void showtime()
{
    for(int i=0; i<k; i++)
    {
        if(pc[i]!=0)
          {
              nr++;
              mat[nr][0]=pc[i];
              mat[nr][1]=po[i];

          }

    }
}

void dfs(int nod)
{
    for(int i=0; i<v[nod].size(); i++)
    {
        if(cost[v[nod][i]]==1 && nivel[v[nod][i]]<nivel[nod]-1)
        {
            nr++;
            int z=0,j;
            for( j=k-1; pc[j]!=v[nod][i]; j--)
            {
                afis[z]=po[j];
                po[j]=0;
                pc[j]=0;
                z++;
            }
            afis[z++]=pc[j]; pc[j]=0;
            afis[z++]=po[j]; po[j]=0;
            sort(afis, afis+z);
            for(int x=0; x<z; x++)
                mat[nr][x]=afis[x];
            for(int x=0; x<z; x++)
                afis[x]=0;

        }else
        if(cost[v[nod][i]]==0)
        {
            nivel[v[nod][i]]=nivel[nod]+1;
            cost[v[nod][i]]=1;
            pc[k]=nod;
            po[k]=v[nod][i];
            k++;
            t[v[nod][i]]=nod;
            dfs(v[nod][i]);
        }
    }
}

int main()
{
    ifstream in("biconex.in");
    int i,j,x,y;
    in>>n>>m;
    for(i=0; i<m; i++)
    {
        in>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    in.close();
    cost[1]=1;
    nivel[1]=1;
    dfs(1);
    showtime();
    out<<nr<<endl;
   for(i=1; i<=nr; i++)
    {
        j=0;
        while(mat[i][j]!=0)
        {
            out<<mat[i][j]<<" ";
            j++;
        }
        out<<endl;
    }
    out.close();
    return 0;
}