Cod sursa(job #1631182)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 5 martie 2016 13:38:02
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <iomanip>
#define MOD 9917
#define NMAX 100005
#define INF 0x3f3f3f3f
#define pb push_back

using namespace std;

FILE *fin = freopen("biconex.in", "r", stdin);
FILE *fout = freopen("biconex.out", "w", stdout);

typedef pair<int, int> pii;

vector<int> v[NMAX];
int dfn[NMAX], low[NMAX], nr;
vector<vector<int> > C;
stack<pii> st;

void DFS(int x, int p);
void add_comp(int x, int y);

int main() {
	int n, i, x, y, a, b, sum = 0, m, j;

	cin >> n >> m;

	for (i = 0; i<m; ++i) {
		cin >> x >> y;
		v[x].pb(y);
		v[y].pb(x);
	}

	memset(dfn, -1, sizeof(dfn));
	DFS(1, 0);

	cout << C.size() << '\n';
	for (i = 0; i<C.size(); ++i) {
		sort(C[i].begin(), C[i].end());

		for (j = 0; j<C[i].size(); ++j)
			if (j == 0 || j>0 && C[i][j] != C[i][j - 1])
				cout << C[i][j] << ' ';
		cout << '\n';
	}

	return 0;
}

void add_comp(int x, int y) {
	int x1, y1;
	vector<int> comp;
	do {
		x1 = st.top().first;
		y1 = st.top().second;
		st.pop();
		comp.pb(x1);
		comp.pb(y1);
	} while (x1 != x || y1 != y);

	C.pb(comp);
}

void DFS(int x, int p) {
	vector<int>::iterator it;

	dfn[x] = low[x] = nr++;
	for (it = v[x].begin(); it != v[x].end(); ++it) {
		if (*it == p)
			continue;
		if (dfn[*it] == -1) {
			st.push({ x, *it });
			DFS(*it, x);
			low[x] = min(low[x], low[*it]);

			if (low[*it] >= dfn[x])
				add_comp(x, *it);
		}
		else
			low[x] = min(low[x], dfn[*it]);
	}
}