Cod sursa(job #2373952)

Utilizator AndreosAndrei Otetea Andreos Data 7 martie 2019 16:08:34
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.09 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define NMAX 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<int>G[NMAX];
vector<int>dfs_discover,dfs_low,articulation_vertex,dfs_parent;
vector<vector<int> >rez;
stack<pair<int,int> >st;
int time,dfsRoot,rootChildren;
void smecher_sa_moara_mama(int u,int v)
{
    vector<int>sol;
    int x,y;
    x=y=0;
    do
    {
        x=st.top().first;
        y=st.top().second;
        sol.push_back(x);
        sol.push_back(y);
        st.pop();
    }
    while(x!=u || y!=v);
    rez.push_back(sol);
}
void articulationPoint(int u)
{
    int v,j;
    time++;
    dfs_discover[u]=dfs_low[u]=time;
    for(j=0;j<G[u].size();++j)
    {
        v=G[u][j];
        if(!dfs_discover[v])
        {
            dfs_parent[v]=u;
            if(u==dfsRoot)
                rootChildren++;
            st.push(make_pair(u,v));
            articulationPoint(v);
            if(dfs_low[v]>=dfs_discover[u])
            {
                articulation_vertex[u]=1;
                smecher_sa_moara_mama(u,v);
            }
            dfs_low[u]=min(dfs_low[u],dfs_low[v]);
        }
        else
        {
            if(dfs_parent[u]!=v)
                dfs_low[u]=min(dfs_low[u],dfs_discover[v]);
        }
    }
}
int main()
{
    int u,v,i,j,m,n;
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs_parent.assign(n+1,0);
    dfs_low.assign(n+1,0);
    dfs_discover.assign(n+1,0);
    articulation_vertex.assign(n+1,0);
    for(i=1;i<=n;++i)
        if(dfs_discover[i]==0)
        {
            dfsRoot=i;
            rootChildren=0;
            articulationPoint(i);
            articulation_vertex[dfsRoot]=rootChildren>1;
        }
    for(i=0;i<rez.size();++i)
    {
        sort(rez[i].begin(),rez[i].end());
        for(j=0;j<rez[i].size();++j)
            if(rez[i][j]!=rez[i][j-1])
                fout<<rez[i][j]<<" ";
        fout<<"\n";
    }
    return 0;
}