Cod sursa(job #1757140)

Utilizator dtoniucDaniel Toniuc dtoniuc Data 14 septembrie 2016 16:33:54
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.76 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

typedef struct result
{
	int number = 0;
	vector<vector<int>*> solution;
}Result;

void AddToResult(int x, int child, stack<int>* stack, Result* result);

void DFS(int parent, int x, vector<int> *graph, bool *marked, int *depth, int *lowPoint, stack<int>* stack, Result* result);
void CreateGraph(int m, vector<int>* graph, ifstream& fin);

int main()
{
    ifstream fin;
    ofstream fout;
    fout.open("biconex.out");
    fin.open("biconex.in");

    int n, m;
    fin >> n >> m;

    vector<int>* graph = new vector<int>[n + 1]();
    bool *marked = new bool[n + 1]();
    int *depth = new int[n + 1]();
    int *lowPoint = new int[n + 1]();

    CreateGraph(m, graph, fin);

    depth[0] = -1;
    Result* result = new Result();
    for(int i = 1; i <= n; i++)
    {
    	if(!marked[i])
    	{
    		stack<int>* st = new stack<int>();
    		DFS(0, i, graph, marked, depth, lowPoint, st, result);
    		if(st->size() > 1)
    		{
    			result->solution.push_back(new vector<int>());
				result->number++;
				vector<int>* last = result->solution[result->solution.size() - 1];

				while(!st->empty())
				{
					last->push_back(st->top());
					st->pop();
				}
    		}
    	}

    }

    fout << result->number << "\n";
    for(int i = 0; i < result->number; i++)
    {
    	for(int j = 0; j < result->solution[i]->size(); j++)
    	{
    		fout << (*(result->solution[i]))[j] << " ";
    	}
    	fout << "\n";
    }

    fin.close();
    fout.close();
    return 0;
}

void DFS(int parent, int x, vector<int> *graph, bool *marked, int *depth, int *lowPoint, stack<int>* stack, Result* result)
{
	depth[x] = depth[parent] + 1;
	lowPoint[x] = depth[x];
	marked[x] = true;
	stack->push(x);

	bool isArticulation = false;
	for(int i = 0; i < graph[x].size(); i++)
	{
		int node = graph[x][i];
		if(!marked[node])
		{

			DFS(x, node, graph, marked, depth, lowPoint, stack, result);
			if(lowPoint[node] >= depth[x])
			{
				if ((parent != 0) || (parent == 0 && graph[x].size() > 1))
				{
					AddToResult(x, node, stack, result);
				}
			}
			lowPoint[x] = min(lowPoint[x], lowPoint[node]);
		}
		else if (node != parent)
		{
			lowPoint[x] = min(lowPoint[x], depth[node]);
		}
	}
}

void AddToResult(int x, int child, stack<int>* stack, Result* result)
{
	result->solution.push_back(new vector<int>());
	result->number++;

	vector<int>* last = result->solution[result->solution.size() - 1];

	while(stack->top() != child)
	{
		last->push_back(stack->top());
		stack->pop();
	}

	last->push_back(child);
	stack->pop();

	last->push_back(x);
}

void CreateGraph(int m, vector<int>* graph, ifstream& fin)
{
	int x, y;
	for(int i = 1; i <= m; i++)
	{
		fin >> x >> y;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
}