Cod sursa(job #2368709)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 5 martie 2019 17:26:07
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.93 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

const int NMAX = 100002;

int task;
int N,M;
int x,y;

vector <int> Ad[NMAX];
vector <int> S;
vector <int> Comp[NMAX];

vector <pair<int,int> > m;
vector <int> Nc;
int nr_comp;
int ct;

int disc[NMAX];
int low[NMAX];
int index;

void DFS1(int nod,int parent)
{
    disc[nod] = low[nod] = ++index;
    for(int i=0;i<Ad[nod].size();++i)
    {
        int w=Ad[nod][i];
        if(!disc[w])
        {
            S.push_back(w);
            DFS1(w,nod);
            low[nod]=min(low[nod],low[w]);
            if(low[w]>=disc[nod])
            {
                nr_comp++;
                S.push_back(nod);
                while(!S.empty() && S.back()!=w )
                {
                    Comp[nr_comp].push_back(S.back());
                    S.pop_back();
                }
                if(!S.empty())
                {
                    Comp[nr_comp].push_back(S.back());
                    S.pop_back();
                }
            }
        }
        else if(w!=parent) low[nod]=min(low[nod],disc[w]);
    }
}

void DFS2(int nod,int parent)
{
    disc[nod] = low[nod] = ++index;
    for(int i=0;i<Ad[nod].size();++i)
    {
        int w=Ad[nod][i];
        if(!disc[w])
        {
            if(nod==1)ct++;
            DFS2(w,nod);
            low[nod]=min(low[nod],low[w]);
            if(low[w]>=disc[nod] && nod!=1)
            {
               Nc.push_back(nod);
            }
        }
        else if(w!=parent) low[nod]=min(low[nod],disc[w]);
    }
}

void DFS3(int nod,int parent)
{
    disc[nod] = low[nod] = ++index;
    for(int i=0;i<Ad[nod].size();++i)
    {
        int w=Ad[nod][i];
        if(!disc[w])
        {

            DFS3(w,nod);
            low[nod]=min(low[nod],low[w]);
            if(low[w]>disc[nod])
            {
               m.push_back(make_pair(nod,w));
            }
        }
        else if(w!=parent) low[nod]=min(low[nod],disc[w]);
    }
}

void Read()
{
    //fin>>task;
    task=1;
    fin>>N>>M;
    for(int i=1;i<=N;++i)
    {
        fin>>x>>y;
        Ad[x].push_back(y);
        Ad[y].push_back(x);
    }
    fin.close();
}
void Do()
{
    if(task==1)
    {
        DFS1(1,0);
        fout<<nr_comp<<"\n";
        for(int i=1;i<=nr_comp;++i){fout<<Comp[i].size()<<" ";
            for(int j=0;j<Comp[i].size();++j)
            fout<<Comp[i][j]<<" ";fout<<"\n";}
    }
    if(task==2)
    {
        DFS2(1,0);
        if(ct>=2)Nc.push_back(1);
        fout<<Nc.size()<<"\n";
        for(int i=0;i<Nc.size();++i)
            fout<<Nc[i]<<" ";
    }
    if(task==3)
    {
        DFS3(1,0);
        fout<<m.size()<<"\n";
        for(int i=0;i<m.size();++i)fout<<m[i].first<<" "<<m[i].second<<"\n";
    }
}
int main()
{
    Read();
    Do();
    return 0;
}