Cod sursa(job #934477)

Utilizator emi58Emanuel Scirlet emi58 Data 30 martie 2013 18:01:13
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include<fstream>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
#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() {
    f>>n>>m;
	for (int i = 1; i <= m; i++) {
		int p, q;

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

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

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

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

            dfs(*it);

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

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

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

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

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

int main() {

    read();

    dfs(1);

	write();

	return 0;
}