Cod sursa(job #2616264)

Utilizator ViAlexVisan Alexandru ViAlex Data 17 mai 2020 20:30:10
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include<bits/stdc++.h>
using namespace std;


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


int num_nodes,num_edges;
vector<int> graph[100000];
vector<int> dfs_graph[100000];
vector<vector<int>> biconnected;
bool visited[100000];
int parent[100000];
int depth[100000];
int lowest_depth[100000];
int current_time=0;


void createDfsTree(int node){
	depth[node]=current_time;
	lowest_depth[node]=current_time;
	current_time++;
	visited[node]=true;

	for(int child:graph[node]){
		if(!visited[child]){
			dfs_graph[node].push_back(child);
			parent[child]=node;
			createDfsTree(child);
			lowest_depth[node]=min(lowest_depth[node],lowest_depth[child]);
		}
		else if(child!=parent[node]){
			lowest_depth[node]=min(lowest_depth[node],depth[child]);
		}
	}
}

void addSubgraph(int node,vector<int>&to_add){
	to_add.push_back(node);
	for(int a:dfs_graph[node])
		addSubgraph(a,to_add);
}

void findBiconnected(int node){

	bool root=false;
	if(parent[node]==-1)
		root=true;
	for(int i=0;i<dfs_graph[node].size();i++){
		int child=dfs_graph[node][i];
		

		findBiconnected(child);


		if((!root && lowest_depth[child]>=depth[node]) || (root && dfs_graph[node].size()>=2)){
			vector<int> comp;
			dfs_graph[node].erase(dfs_graph[node].begin()+i);
			i--;
			comp.push_back(node);
			addSubgraph(child,comp);	
			biconnected.push_back(comp);
		}
	}
}

void read(){
	in>>num_nodes>>num_edges;
	int a,b;
	for(int i=0;i<num_edges;i++){
		in>>a>>b;
		graph[a-1].push_back(b-1);
		graph[b-1].push_back(a-1);
	}

	for(int i=0;i<num_nodes;i++)
		parent[i]=-1;
}


void solve(){
	createDfsTree(0);
	findBiconnected(0);
	vector<int> remaining;
	addSubgraph(0,remaining);
	biconnected.push_back(remaining);
	out<<biconnected.size()<<endl;
	for(int i=0;i<biconnected.size();i++){
		for(int a:biconnected[i])
			out<<a+1<<" ";
		out<<endl;
	}
}


int main(){
	read();
	solve();
	return 0;
}