Cod sursa(job #1552731)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 18 decembrie 2015 15:38:32
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <fstream>
#include <vector>
#include <stack>
#include <string.h>

#define NMax 100010

using namespace std;

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

int nodes, edges, prenum[NMax], low[NMax], pren, father[NMax], numComp;
bool mark[NMax], alreadyDisp[NMax];
vector<int> G[NMax], biComp[NMax];

struct edge {
	int n1;
	int n2;
};
stack<edge> mStack;

int getMin(int a, int b)
{
	if (a < b)
		return a;
	return b;
}

void DFS(int node)
{
	mark[node] = true;

	prenum[node] = ++pren;
	low[node] = pren;

	for (vector<int>::iterator it = G[node].begin(); it != G[node].end(); it++) {
		if (!mark[*it]) {
			edge edg;
			edg.n1 = node;
			edg.n2 = *it;
			mStack.push(edg);

			father[*it] = node;

			DFS(*it);

			low[node] = getMin(low[node], low[*it]);

			if (low[*it] >= prenum[node]) {
				++numComp;

				while (mStack.top().n1 != node && mStack.top().n2 != *it) {
					biComp[numComp].push_back(mStack.top().n1);
					biComp[numComp].push_back(mStack.top().n2);
					mStack.pop();
				}
				biComp[numComp].push_back(node);
				biComp[numComp].push_back(*it);
			}
		}
		else if (father[node] != *it)
			low[node] = getMin(low[node], low[*it]);
	}

	
}

int main()
{
	f >> nodes >> edges;

	int n1, n2;

	for (int i = 1; i <= edges; i++) {
		f >> n1 >> n2;

		G[n1].push_back(n2);
		G[n2].push_back(n1);
	}

	for (int i = 1; i <= nodes; i++) {
		if (!mark[i])
			DFS(i);

		g << numComp << "\n";

		for (int i = 1; i <= numComp; i++) {
			memset(alreadyDisp, 0, sizeof(alreadyDisp));

			for (vector<int>::iterator it = biComp[i].begin(); it != biComp[i].end(); it++) {
				if (!alreadyDisp[*it]) {
					g << *it << " ";
					alreadyDisp[*it] = true;
				}
			}
			g << "\n";
		}

		return 0;
	}
}