Cod sursa(job #2261743)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 16 octombrie 2018 17:00:48
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include <bits/stdc++.h>
#define Nmax 100001
using namespace std;

ifstream f("biconex.in");
ofstream fout("auxiliary_file.txt");
ofstream g("biconex.out");

int N,M,x,y,no_bic_comp;
list <int> G[Nmax];
int lvl[Nmax];
int low[Nmax];
vector <int> v;
stack <pair <int,int> > st;

void read()
{
    f>>N>>M;
    int x,y;
    while(M--)
    {
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void DFS(int node, int parent)
{
    low[node]=lvl[node]=lvl[parent]+1;

    for(const auto &it:G[node])
        if(it!=parent)
        {
            if(!lvl[it])
            {
                st.push({node,it});
                DFS(it,node);
                low[node]=min(low[node],low[it]);

                if(low[it]>=lvl[node])
                {
                    ++no_bic_comp;
                    v.clear();
                    do
                    {
                        x=st.top().first;
                        y=st.top().second;
                        st.pop();
                        v.push_back(x);
                        v.push_back(y);

                    }while(x!=node and y!=it);

                    sort(v.begin(),v.end());
                    v.erase(unique(v.begin(),v.end()),v.end());
                    for(const auto &idx:v)
                        fout<<idx<<' ';
                    fout<<'\n';
                }
            }
            else
                low[node]=min(low[node],low[it]);
        }
}

void print()
{
    g<<no_bic_comp<<'\n';
    fout.close();
    ifstream fin("auxiliary_file.txt");
    char s[1000001];
    for(int idx=1;idx<=no_bic_comp;++idx)
    {
        fin.getline(s,1000001);
        g<<s<<'\n';
    }
}

int main()
{
    read();
    DFS(1,0);
    print();

    return 0;
}