Cod sursa(job #2667558)

Utilizator speedypleathGheorghe Andrei speedypleath Data 3 noiembrie 2020 17:14:33
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector<int> graf[200005];
stack<int> s;
vector<vector<int>> sol;
int n,m,nr;
int nivel[200005],low[200005];
void component(int node, int son)
{
    nr++;
	vector<int> comp;
	int c;
	do
    {
		c = s.top();
		s.pop();
		comp.emplace_back(c);
	}
	while (c != son);
	comp.emplace_back(node);
	sol.emplace_back(comp);
}
void dfs(int node, int parent, int idc)
{
    nivel[node] = idc;
    low[node] = idc;
    for(auto it:graf[node]){
        if(it==parent)
            continue;
        if(!nivel[it])
        {
            s.push(it);
            dfs(it,node,idc+1);
            low[node] = min(low[node],low[it]);
            if(low[it]>=nivel[node])
                component(node,it);
        }
        else
            low[node] = min(low[node],low[it]);
    }
}
int main()
{
    in>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        in>>a>>b;
        graf[a].emplace_back(b);
        graf[b].emplace_back(a);
    }
/*    for(int i=1;i<=n;i++)
    {
        cout<<i<<':';
        for(auto it:graf[i])
            cout<<it<<' ';
        cout<<endl;
    }*/
    dfs(1,0,1);
    out<<nr<<'\n';
    for(auto i=0;i<nr;i++)
    {
        for(auto it:sol[i])
            out<<it<<' ';
        out<<'\n';
    }
    return 0;
}