Cod sursa(job #553869)

Utilizator savimSerban Andrei Stan savim Data 14 martie 2011 13:11:13
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX_N 100010

int n, m, k, t;
int use[MAX_N], depth[MAX_N], up[MAX_N];
int stack[2][MAX_N];

vector <int> A[MAX_N], S[MAX_N];

void read() {
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);

	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int p, q;
		scanf("%d %d", &p, &q);

		A[p].push_back(q);
		A[q].push_back(p);
	}
}

void dfs(int vertex) {
    use[vertex] = 1;
    up[vertex] = depth[vertex];

    for (vector <int>::iterator it = A[vertex].begin(); it != A[vertex].end(); ++it)
        if (use[*it] == 0) {
            depth[*it] = depth[vertex] + 1;

            stack[0][++t] = vertex;
            stack[1][t] = *it;

            dfs(*it);

            if (up[*it] >= depth[vertex]) { //am gasit o componenta biconexa
                k++;

                while (!(stack[0][t] == vertex && stack[1][t] == *it)) {
                    S[k].push_back(stack[1][t]);
                    t--;
                }

                S[k].push_back(vertex);
                S[k].push_back(*it);
                t--;
            }

            up[vertex] = min(up[vertex], up[*it]);
        }
        else
            up[vertex] = min(up[vertex], depth[*it]);
}

void write() {
	printf("%d\n", k);
              
	for (int i = 1; i <= k; i++) {
		for (vector <int>::iterator it = S[i].begin(); it != S[i].end(); ++it)
			printf("%d ", *it);
		printf("\n");
	}
}

int main() {

    read();

    dfs(1);

	write();

	return 0;
}