Cod sursa(job #2150216)

Utilizator AlexTheDagonBogdan Tudor AlexTheDagon Data 3 martie 2018 12:49:01
Problema Componente biconexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 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;
vector<set<int> > comp;
void getBcc(int node,int son)
{
    set<int> s;
    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);
    comp.pb(s);
}
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])
            {
                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);
    }
    dfs(1,0);
    out<<comp.size()<<'\n';
    for(auto s:comp)
    {
        for(auto i:s)out<<i<<" ";
        out<<'\n';
    }
    return 0;
}