Cod sursa(job #632021)

Utilizator sergiupPopescu Sergiu sergiup Data 10 noiembrie 2011 01:30:28
Problema Componente biconexe Scor 58
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;
#define MAXN 100005

int n,m;
vector<int> g[MAXN];
int depth[MAXN],low[MAXN],parent[MAXN];
bool viz[MAXN];
vector<vector<int> > rez;

struct edge {
	int x,y;
};

stack<edge> st;

void output(int u,int v) {
	edge e;
	vector<int> r;

	do {
		e = st.top();
		st.pop();
		if (r.size() == 0) {
			r.push_back(e.y);
		} else if (r[r.size() - 1] != e.y) {
			r.push_back(e.y);
		}

	} while (e.x != u && e.y != v);
	if (r.size() == 1) {
		r.push_back(e.x);
	}

	rez.push_back(r);
}

void dfs(int node,int d) {
	viz[node] = 1;
	depth[node] = d;
	low[node] = d;

	for (int i = 0 ; i < g[node].size() ; ++i)  {
		if (!viz[g[node][i]]) {
			edge e;
			e.x = node;
			e.y = g[node][i];
			st.push(e);
			parent[g[node][i]] = node;
			dfs(g[node][i],d + 1);
			if (low[g[node][i]] >= depth[node]) {
				output(node,g[node][i]);
			}
			low[node] = min(low[node],low[g[node][i]]);
		} else if (g[node][i] != parent[node] && depth[g[node][i]] < depth[node]) {
			edge e;
			e.x = node;
			e.y = g[node][i];
			st.push(e);

			low[node] = min(low[node],depth[g[node][i]]);
		}
	}

}

int main() {
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	scanf("%d %d",&n,&m);

	int x,y;
	for (int i = 0 ; i < m ; ++i) {
		scanf("%d %d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}

	for (int i = 1; i <= n ; ++i) {
		if (!viz[i]) {
			dfs(i,1);
		}
	}

	printf("%d\n",rez.size());

	for (int i = 0; i < rez.size() ; ++i) {
		for (int j = 0 ; j < rez[i].size() ; ++j) {
			printf("%d ",rez[i][j]);
		}
		printf("\n");
	}

	return 0;
}