Cod sursa(job #2676648)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 24 noiembrie 2020 18:43:19
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
//
//  main.cpp
//  biconex
//
//  Created by she on 24.11.2020.
//

#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
 
using namespace std ;
 
const int N = 100000 + 7 ;
int n ;
int m ;
int d[N] ;
int mn[N] ;
vector<int> g[N] ;
vector<pair<int, int>> stk ;
vector<vector<int>> comps ;
 
void dfs(int a) {
	mn[a] = d[a] ;
	for (auto &b : g[a]) {
		if (d[b] == -1) {
			stk.push_back({a, b}) ;
			d[b] = 1 + d[a] ;
			dfs(b) ;
			mn[a] = min(mn[a], mn[b]) ;
			if (d[a] <= mn[b]) {
				vector<int> nodes ;
				nodes.push_back(a) ;
				nodes.push_back(b) ;
				while (stk.back() != make_pair(a, b)) {
					nodes.push_back(stk.back().first) ;
					nodes.push_back(stk.back().second) ;
					stk.pop_back() ;
				}
				stk.pop_back() ;
				sort(nodes.begin(), nodes.end()) ;
				comps.push_back({nodes[0]}) ;
				for (int i = 1 ; i < (int) nodes.size() ; i++) {
					if (nodes[i - 1] != nodes[i]) {
						comps.back().push_back(nodes[i]) ;
					}
				}
			}
		} else {
			if (d[b] < d[a] - 1) {
				mn[a] = min(mn[a], d[b]) ;
			}
		}
	}
}
 
int main() {
	freopen ("biconex.in", "r", stdin) ;
	freopen ("biconex.out", "w", stdout) ;
 
	scanf("%d %d", &n, &m) ;
	for (int i = 1 ; i <= n ; i++) {
		d[i] = -1 ;
	}
	for (int i = 1 ; i <= m ; i++) {
		int x, y ;
		scanf("%d %d", &x, &y) ;
		g[x].push_back(y) ;
		g[y].push_back(x) ;
	}
	for (int i = 1 ; i <= n ; i++) {
		if (d[i] == -1) {
			d[i] = 0 ;
			dfs(i) ;
		}
	}
	printf("%d\n", (int) comps.size()) ;
	for (auto &vec : comps) {
		for (auto &x : vec) {
			printf("%d ", x) ;
		}
		printf("\n") ;
	}
}