Cod sursa(job #1735788)

Utilizator theo.stoicanTheodor Stoican theo.stoican Data 31 iulie 2016 00:08:32
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cstdio>
#include <algorithm>

using namespace std;

vector<vector<int> > graph;
int n,m;
vector<int> idx;
vector<int> lowlink;
stack<pair<int,int> > s;
vector<vector<int> > bc;

void store_bc(int x1, int x2)
{
	int n1, n2;
	bc.resize(bc.size()+1);
	do {
		//if (s.empty())
		//	break;
		n1 = s.top().first;
		n2 = s.top().second;
		s.pop();
		bc[bc.size()-1].push_back(n1);
		bc[bc.size()-1].push_back(n2);
	} while (n1 != x1 || n2 != x2);
}

//num nu trebuie sa creasca non-stop, deoarece nu-mi foloseste
//la determinarea CB, cum era la CTC
void dfs(int node, int prevNode, int num)
{
	//cout<<node<<endl;
	idx[node]=num;
	lowlink[node] = num;
	for (int i = 0; i < graph[node].size(); i++)
	{
		if (graph[node][i] == prevNode)
			continue;
		if (idx[graph[node][i]] == -1)
		{
			s.push(make_pair(node, graph[node][i]));
			dfs(graph[node][i], node, num+1);
			lowlink[node] = min (lowlink[node], lowlink[graph[node][i]]);
			//daca e punct de articulatie
			if (lowlink[graph[node][i]] >= idx[node])
			{
				store_bc(node, graph[node][i]);
			}
		}
		else
		{
			lowlink[node] = min (lowlink[node], idx[graph[node][i]]);
		}
	}
}

int main()
{
	int x,y;
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
	scanf("%d %d", &n,  &m);
	graph.resize(n+1);
	idx.resize(n+1, -1);
	lowlink.resize(n+1, -1);
	for (int i = 1; i <= m; i++)
	{
		scanf ("%d %d", &x, &y);
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	dfs(1,0,0);
	cout<<bc.size()<<"\n";
	for (int i = 0; i < bc.size();i++)
	{
		sort(bc[i].begin(), bc[i].end());
		bc[i].erase(unique(bc[i].begin(), bc[i].end()), bc[i].end());
		for (int j = 0 ; j < bc[i].size(); j++)
		{
			cout<<bc[i][j]<<" ";
		}
		cout<<"\n";
	}
}