Cod sursa(job #1460317)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 12 iulie 2015 13:07:45
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#define min(x, y) (x < y ? x : y)
#define MAX 100005
using namespace std;

typedef struct{
	int s, d;
} Edge;

vector<int> l[MAX];
vector< vector<int> > C;
vector<Edge> s;
Edge aux;
int n, m, i, j, x, y, viz[MAX], low[MAX];

void con(int x, int y);
void dfs(int x, int f, int depth);

int main(){
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(i = 1; i <= n; i++)
		viz[i] = -1;
	for(i = 0; i < m; i++){
		scanf("%d%d", &x, &y);
		l[x].push_back(y);
		l[y].push_back(x);
	}
	dfs(1, 0, 0);
	
	printf("%d\n", C.size());
	for(i = 0; i < C.size(); i++){
		sort(C[i].begin(), C[i].end());
		printf("%d ", C[i][0]);
		for(j = 1; j < C[i].size(); j++)
			if(C[i][j] != C[i][j - 1])
				printf("%d ", C[i][j]);
		printf("\n");
	}
	return 0;
}

void con(int x, int y){
	vector<int> con;
	do{
		aux = s.back();
		s.pop_back();
		con.push_back(aux.s);
		con.push_back(aux.d);
	}while(aux.s != x || aux.d != y);
	C.push_back(con);
}

void dfs(int x, int f, int depth){
	vector<int>::iterator it;
	viz[x] = low[x] = depth;
	for(it = l[x].begin(); it < l[x].end(); it++){
		if(*it == f)
			continue;
		if(viz[*it] == -1){
			aux.s = x;
			aux.d = *it;
			s.push_back(aux);
			dfs(*it, x, depth + 1);
			low[x] = min(low[x], low[*it]);
			if(low[*it] >= viz[x])
				con(x, *it);
		}
		else
			low[x] = min(low[x], viz[*it]);
	}
}