Cod sursa(job #2557128)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 25 februarie 2020 15:50:54
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <fstream>
using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

const int N = 100000;

struct nod{
	int num, low, parent;
} nodes[N+1];
bool visited[N+1];
bool articulation[N+1];

vector <int> g[N+1];
vector <int> stiva;
vector <int> comp[N+1];
int timp, rootChildren, root;
int compNr;

void dfs(int node){
	stiva.push_back(node);
	visited[node] = true;
	nodes[node].low = nodes[node].num = timp++;
	for(int p=0; p<(int)g[node].size(); p++){
		int next = g[node][p];
		if(!visited[next]){
			nodes[next].parent = node;
			if(node == root)
				rootChildren++;
			dfs(next);
			if(nodes[node].num <= nodes[next].low){
				articulation[node] = true;
				compNr++;
				while(stiva.back() != next){
					comp[compNr].push_back(stiva.back());
					stiva.pop_back();
				}
				comp[compNr].push_back(next);
				comp[compNr].push_back(node);
				stiva.pop_back();
			}
			nodes[node].low = min(nodes[node].low, nodes[next].low);
		}
		else if(next != nodes[node].parent)
			nodes[node].low = min(nodes[node].low, nodes[next].num);
	}
}

int main()
{
	int n,m,i,x,y;
	fin >> n >> m;
	for(i=0; i<m; i++){
		fin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(i=1; i<=n; i++)
		if(!visited[i]){
			timp = 0, rootChildren = 0, root = i;
			dfs(i);
			articulation[i] = (rootChildren > 1);
		}

	fout << compNr << "\n";
	for(i=1; i<=compNr; i++){
		for(int j=0; j<(int)comp[i].size(); j++)
			fout << comp[i][j] << " ";
		fout << "\n";
	}
	return 0;
}