Cod sursa(job #3128534)

Utilizator AlexandruBenescuAlexandru Benescu AlexandruBenescu Data 9 mai 2023 20:09:26
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include<bits/stdc++.h>
#define L 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");

int n, m;
vector <int> G[L], ans[L];
int lev[L], t[L], s[L];
int r, st;

void dfs(int node){
	s[++st] = node;
	for (auto it : G[node])
		if (lev[it])
      lev[node] = min(lev[node], t[it]);
    else{
			int x = st;
			t[it] = lev[it] = t[node] + 1;
			dfs(it);
			lev[node] = min(lev[it], lev[node]);
			if (lev[it] >= t[node]){
				ans[++r].push_back(node);
				while (st > x)
          ans[r].push_back(s[st--]);
			}
		}
}

int main(){
	fin >> n >> m;
	for (int i = 1; i <= m; i++){
    int a, b;
		fin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	t[1] = lev[1] = 1;
	dfs(1);
	fout << r << "\n";
	for (int i = 1; i <= r; i++){
    for(auto it : ans[i])
      fout << it << " ";
    fout << "\n";
	}
	return 0;
}