Cod sursa(job #1599315)

Utilizator qwertyuiTudor-Stefan Berbinschi qwertyui Data 13 februarie 2016 19:22:02
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.25 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <utility>

using namespace std;

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

//Given limits
#define MAXN 100050
#define MAXM 200050


//Given variables
vector <int> edge[MAXN];
int N, M;

//Solution Variables
int depth_order[MAXN], first_from_x[MAXN];
vector < vector <int> > biconex_components;

stack < pair <int, int> > edges_work;


//tool functions
void initialize_array (int x[], int _size, int value)
{
	for (int i = 0; i <= _size; ++i)
		x[i] = value;
}

//SOLUTION / Complexity: O(N+M)

void push_solution (int x, int y)
{
	vector <int> to_push;
	int temp_x, temp_y;
	do
	{
		temp_x = edges_work.top().first;
		temp_y = edges_work.top().second;
		to_push.push_back(temp_x);
		to_push.push_back(temp_y);
		edges_work.pop();
	}
	while (temp_x != x || temp_y != y);
	sort(to_push.begin(), to_push.end());
	to_push.erase( unique( to_push.begin(), to_push.end() ), to_push.end() );
	biconex_components.push_back(to_push);
}

void DFS (int node, int ancestor, int order)
{
	depth_order[node] = first_from_x[node] = order;
	for (int i = 0; i < edge[node].size(); ++i)
	{
		if (depth_order[edge[node][i]] == -1)
		{
			edges_work.push(make_pair(node, edge[node][i]));
            DFS(edge[node][i], node, order+1);
            first_from_x[node] = (first_from_x[node] < first_from_x[edge[node][i]]) ? (first_from_x[node]) : (first_from_x[edge[node][i]]);
            if (first_from_x[edge[node][i]] >= depth_order[node])
				push_solution(node, edge[node][i]);
		}
		else
			first_from_x[node] = (first_from_x[node] < depth_order[edge[node][i]]) ? (first_from_x[node]) : (depth_order[edge[node][i]]);
	}
}

int main()
{
    fin >>N >>M;

    for (int i = 0; i < M; ++i)
    {
        int x, y;
        fin >>x >>y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }

    initialize_array (depth_order, N+1, -1);

    DFS (1, 0, 0);

    fout <<biconex_components.size() <<'\n' ;
    for (int i = 0; i < biconex_components.size(); ++i)
	{
		for (int j = 0; j < biconex_components[i].size(); ++j)
			fout <<biconex_components[i][j] <<' ';
		fout <<'\n';
	}

    return 0;
}