Cod sursa(job #1563595)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 6 ianuarie 2016 12:44:26
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <cstdio>
#include <vector>
#define MAXN 100050

using namespace std;

vector<int> graf[MAXN];
vector<vector<int> > sol;
vector<pair<int, int> > stiva;
int n, m;
int depth[MAXN], low[MAXN], viz[MAXN];

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

void updateSolution(int nod, int y)
{
    int cx, cy;
    vector<int> newSol;

    while (!stiva.empty()) {
		cx = stiva.back().first;
		cy = stiva.back().second;
		stiva.pop_back();
		newSol.push_back(cy);
		if (nod == cx && y == cy)
			break;
    }
    newSol.push_back(nod);
    sol.push_back(newSol);
}

void dfs(int nod, int d)
{
	int eArticulatie = 0;
	viz[nod] = 1;
	depth[nod] = d;
	low[nod] = d;
	for (int i = 0, t = graf[nod].size(); i < t; i++) {
		int y = graf[nod][i];
		if (!viz[y]) {
			stiva.push_back(make_pair(nod, y));
            dfs(y, d+1);
			low[nod] = min(low[nod], low[y]);
            if (depth[nod] <= low[y]) {
				eArticulatie = 1; /// doar daca nod-ul nu-i root dar nu ne intereseaza
				updateSolution(nod, y);
            }
		}
		else
			low[nod] = min(low[nod], depth[y]);
	}
}

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

int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);

    citire();
    dfs(1, 0);
    afisare();
    return 0;
}