Cod sursa(job #1028156)

Utilizator StickmanLazar Alexandru Stickman Data 13 noiembrie 2013 18:29:46
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

vector <int> v[100001];
int n,m,cost[100001],t[100001],pc[1000001],po[1000001],k,afis[1000001],nr;
ofstream out("biconex.out");
void showtime()
{
    for(int i=0; i<k; i++)
    {
        if(pc[i]!=0)
          {
              nr++;
              while(pc[i]!=0)
                {
                    out<<pc[i]<<" ";
                    i++;
                }
                out<<po[i-1]<<endl;
          }

    }
}

void dfs(int nod)
{
    for(int i=0; i<v[nod].size(); i++)
    {
        if(cost[v[nod][i]]==1 && t[nod]!=v[nod][i] && v[nod][i]<nod)
        {
            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++)
                out<<afis[x]<<" ";
            for(int x=0; x<z; x++)
                afis[x]=0;
            out<<endl;

        }else
        if(cost[v[nod][i]]==0)
        {
            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();
    out<<1<<endl;
    cost[1]=1;
    dfs(1);
    showtime();
    out.close();
    return 0;
}