Cod sursa(job #1771552)

Utilizator sahleancosminSahlean Cosmin sahleancosmin Data 5 octombrie 2016 19:19:04
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <int> matrix[100001],ret[100001];
int n,m,ciclu[100001],st[100001],k,contor;
void df(int x,int inainte,int adancime)
{
    st[++k]=x;
    ciclu[x]=adancime;

    for(vector<int>::iterator i=matrix[x].begin();i!=matrix[x].end();i++)
    {
        if(!ciclu[*i])
        {
             int falsk=k;
            df(*i,x,adancime+1);
            if(ciclu[*i]>=adancime)
            {

            contor++;
           while(k!=falsk) ret[contor].push_back(st[k--]);
            ret[contor].push_back(x);
            }
        }
        if(*i!=inainte) ciclu[x]=min(ciclu[*i],ciclu[x]);
    }
}
int main()
{
    f>>n>>m;
    int x,y;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y;
        matrix[x].push_back(y);
        matrix[y].push_back(x);
    }
    df(1,0,1);
    for(int j=1;j<=contor;j++)
        {
            for(vector<int>::iterator i=ret[j].begin();i!=ret[j].end();i++)
                g<<*i<<" ";
            g<<'\n';
        }

    return 0;
}