Cod sursa(job #2150245)

Utilizator AlexTheDagonBogdan Tudor AlexTheDagon Data 3 martie 2018 13:05:08
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <stack>
#include <bitset>
#define NM 100005
#define pb push_back
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
int n,m,level[NM],lowlink[NM];
stack<pair<int,int> > st;
vector<int> g[NM];
bitset<NM> viz;
set<int> s;
vector<int > v;
int caz,sol;
void getBcc(int node,int son)
{
    int x,y;
    do
    {
        x=st.top().first;
        y=st.top().second;
        s.insert(x);
        s.insert(y);
        st.pop();
    }
    while(node!=x || son!=y);
    for(auto i:s)out<<i<<" ";
    out<<'\n';
    s.clear();
}
void dfs(int node,int father)
{
    viz[node]=1;
    level[node]=level[father]+1;
    lowlink[node]=level[node];
    for(auto fiu:g[node])
    {
        if(!viz[fiu])
        {
            st.push({node,fiu});
            dfs(fiu,node);
            lowlink[node]=min(lowlink[node],lowlink[fiu]);
            if(lowlink[fiu]>=level[node])
            {
                if(caz==1)++sol;
                else getBcc(node,fiu);
            }
        }
        else
        {
            if(fiu!=father)
                lowlink[node]=min(lowlink[node],level[fiu]);
        }
    }
}
int main()
{
    in>>n>>m;
    while(m--)
    {
        int x,y;
        in>>x>>y;
        g[x].pb(y);
        g[y].pb(x);
    }
    caz=1;
    dfs(1,0);
    for(int i=1;i<=n;++i)viz[i]=level[i]=lowlink[i]=0;
    while(!st.empty())st.pop();
    out<<sol<<'\n';
    caz=2;
    dfs(1,0);
    return 0;
}