Cod sursa(job #552506)

Utilizator bixcabc abc bixc Data 12 martie 2011 14:46:37
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;

#define Nmax 100010
#define Mmax 200010

struct muchie {
	int x, y;
} S[Mmax];

int n, m, N, nr, x, y;   
int Tata[Nmax], Niv[Nmax], low[Nmax];
vector <int> V[Nmax], Sol[Nmax];

void citire () {

	int x, y;

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

void dfs (int nod, int niv) {
	
	Niv[nod] = low[nod] = niv;
    
	for (vector <int>::iterator it = V[nod].begin (); it != V[nod].end (); it++) 
		if (*it != Tata[nod]) {
			if (!Niv[*it] && *it != 1) {
				Tata[*it] = nod;
                S[++N].x = nod; S[N].y = *it;    

				dfs (*it, niv + 1);

               if (low[*it] >= niv) {
					++nr;
				    do {
				    	x = S[N].x; y = S[N].y;
					    Sol[nr].push_back (y);		
					    N--; 
					} while (x != nod || y != *it);
                    
					Sol[nr].push_back (x);
				}

			   if (low[nod] > low[*it]) low[nod] = low[*it]; 
			}
			else {
			   if (Niv[*it] < low[nod]) low[nod] = Niv[*it]; 		
			} 			
		} 
}

int main () {

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

	citire ();
	int i;
	for (i = 1; i <= n; i++)
	    if (!Niv[i]) dfs (1, 0);

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

    return 0;
}