Cod sursa(job #1430797)

Utilizator GilgodRobert B Gilgod Data 8 mai 2015 20:23:15
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
#include <vector>
#include <sstream>
#include <bitset>

#define NMAX 100001
#define mkedge(a,b) make_pair(a,b)
#define min(a,b) ((a)<(b))?(a):(b)
typedef std::pair<int, int> edge;

const char IN[] = "biconex.in", OUT[] = "biconex.out";

using namespace std;

vector<int> G[NMAX];
int N, M;

inline void readData() {
	freopen(IN, "r", stdin);
	scanf("%d %d", &N, &M);
	for (int m = 0; m < M; ++m) {
		int s, d;
		scanf("%d %d", &s, &d);
		G[s].push_back(d);
		G[d].push_back(s);
	}
	fclose(stdin);
}



int discovery_time;
stack<edge> s;
int disc_time[NMAX], lowlink[NMAX];

std::ostringstream out;
int nrbc;


inline void pop_biconex(int const u, int const v) {
	edge e;
	edge check = mkedge(u, v);
	bitset<NMAX> added;
	do {
		e = s.top(); s.pop();
		if (!added[e.first]) {
			out << e.first << " "; added[e.first].flip();
		}
		if (!added[e.second]){
			out << e.second << " "; added[e.second].flip();
		}
	} while (check != e);
	out << endl;
	++nrbc;
}

inline void DFS_biconex(int node, int const father){
	disc_time[node] = lowlink[node] = ++discovery_time;
	for (auto &n : G[node]) {
		if (n == father) continue;
		if (!disc_time[n]) {
			s.push(mkedge(node, n));
			DFS_biconex(n, node);
			lowlink[node] = min(lowlink[node], lowlink[n]);
			if (lowlink[n] >= disc_time[node]) {
				//punct de articulatie
				//se poate ajunge la un nod stramos in DFS printr-un copil
				pop_biconex(node, n);
			}
		}
		else lowlink[node] = min(lowlink[node], disc_time[n]);
	}
}

int main() {
	readData();
	for (int i = 1; i <= N; ++i)
		if (!disc_time[i]) DFS_biconex(i, 0);
	freopen(OUT, "w", stdout);
	cout << nrbc << endl << out.str();
	fclose(stdout);
	return 0;
}