Cod sursa(job #1413672)

Utilizator alexandru70Ungurianu Alexandru alexandru70 Data 2 aprilie 2015 00:25:10
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

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

struct Node
{
	int index;
	int parent;
	int lowlink;
	bool on_stack;
};

vector<Node> nodes;

vector<vector<int>> edges;

unsigned index = 0;
stack<int> nodes_unass;

vector<vector<int>> components;

void biconex(int v) {
	nodes[v].index = index++;
	nodes[v].lowlink = nodes[v].index;
	nodes_unass.push(v);
	nodes[v].on_stack = true;

	for(int u:edges[v]) {
		if(nodes[u].index == -1) {
			nodes[u].parent = v;
			biconex(u);
			nodes[v].lowlink = min(nodes[v].lowlink,nodes[u].lowlink);
			
			if(nodes[u].lowlink >= nodes[v].index) {
				components.push_back(vector<int>({v}));
				while(nodes_unass.top() != v) {
					nodes[nodes_unass.top()].on_stack = false;
					components.back().push_back(nodes_unass.top());
					nodes_unass.pop();
				}
			}
		}
		else if (u != nodes[v].parent) {
			nodes[v].lowlink = min(nodes[v].lowlink,nodes[u].index);
		}
	}
}


int main() {
	int n,m;
	in >> n >> m;
	edges.resize(n+1);
	nodes.resize(n+1,{-1,-1});

	for(int i = 0; i < m; ++i) {
		int a,b;
		in >> a >> b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}

	for(int i = 1; i <= n; ++i) {
		if(nodes[i].index == -1) {
			biconex(i);
		}
	}

	out << components.size() << '\n';

	for(auto comp:components) {
		for(int v:comp) {
			out << v << ' ';
		}
		out << '\n';
	}

	return 0;
}