Cod sursa(job #1896804)

Utilizator Consti.001FMI Dranca Constantin Consti.001 Data 28 februarie 2017 22:03:08
Problema Componente biconexe Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

ifstream f("biconex.in");
FILE *g;

int d[100000],low[100000];
int pred[100000], art[100000];

struct muchie
{
    int x;
    int y;
};

stack <struct muchie> stiva;

void citire_date_despre_graf(int &n,int &m, vector <int> *&l)
{
    f>>n>>m;
    l=new vector <int> [n+1];
    for(int i=1;i<=m;i++)
    {
        int x,y;
        f>>x>>y;
        l[x].push_back(y);
        l[y].push_back(x);
    }
}
int timp=0;
void dfs(int nod, vector <int> *l)
{
    timp++;
    d[nod]=low[nod]=timp;
   int nrc=0;
    for(int i=0;i<l[nod].size();i++)
    {
        if(d[l[nod][i]]==0)
        {
            nrc++;
            pred[l[nod][i]]=nod;
            dfs(l[nod][i],l);
            if(low[l[nod][i]]>=d[nod]&&nod!=1)
            {
                art[nod]=1;
            }
            low[nod]=min(low[nod],low[l[nod][i]]);
        struct muchie s;
        s.x=nod;
        s.y=l[nod][i];
        stiva.push(s);
        }
        else
        if(l[nod].size()==1) art[nod]=1;
        else
        if(pred[nod]!=l[nod][i])
        low[nod]=min(low[nod],d[l[nod][i]]);
    }
}

int main()
{
    g=fopen("biconex.out","w");
    fprintf(g,"                                                                                    \n");
    vector <int> *l;
    int n,m;
    citire_date_despre_graf(n,m,l);
    dfs(1,l);
    if(l[1].size()>=2) art[1]=1;
    int nrc=0;
    int okx=0;

    while(!stiva.empty())
    {
        muchie a=stiva.top();
        //fprintf(g,"%d %d\n",a.x,a.y);
        if(okx==0)
        {
            fprintf(g,"%d ",a.x);
            okx=1;
        }
        fprintf(g,"%d ",a.y);
        if(art[a.y]==1)
        {
              fprintf(g,"\n");
              okx=0;
              nrc++;
        }
        stiva.pop();
    }
    fseek(g,0,SEEK_SET);
    fprintf(g,"%d",nrc+1);
    return 0;
}