Cod sursa(job #3137488)

Utilizator thinkphpAdrian Statescu thinkphp Data 13 iunie 2023 08:26:15
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include<stdio.h>
#include<algorithm>
#include <cstring>
using namespace std;

struct nod {int inf; nod *urm;} *v[100111], *sol[100111];
int nrsol, i, viz[100111], u, st[400111], n, m, low[100111], df[100111];


void add(int x,int y){
	nod *p = new nod;
	p->inf = y;
	p->urm = v[x];
	v[x] = p;
}

void citire(){

	int i, x, y;
	FILE *f = fopen("biconex.in", "r");
	fscanf(f,"%d %d",&n,&m);
	
	for(i=1; i<=m; i++){
		fscanf(f,"%d %d",&x,&y);
		add(x, y);
		add(y, x);
	}
	
	fclose(f);
}

void update(int x, int y){

	int xx, yy;
	nrsol++;
	
	do{
		xx = st[u];
		yy = st[u - 1];
		
		nod *p = new nod;
		p->inf = xx;
		p->urm = sol[nrsol];
		sol[nrsol] = p;
		
		p = new nod;
		p->inf = yy;
		p->urm = sol[nrsol];
		sol[nrsol] = p;
		
		u-=2;
	}
	while( yy != x || xx != y );
	
}

void DFS(int nc, int niv, int tata){

	nod *p;
	viz[ nc ] = 1;
	df[nc] = low[nc] = niv;
	
	for(p = v[nc]; p != NULL; p = p->urm){
		if( tata != p->inf ){
			if(!viz[ p->inf ]){
				st[++u] = nc;
				st[++u] = p->inf;
				
				DFS(p->inf, niv+1, nc);
				
				if( ! (low[p->inf] < df[nc] ) )
					update(nc, p->inf);
				
				low[nc] = min( low[nc], low[p->inf] );
			}
			
			else
				low[nc] = min( low[nc], df[p->inf]);
			
			
		}
	}
	
}

void solve(){
	int i;
	for(i=1; i<=m; i++)
		if( !viz[i] )
			DFS(i, 1, 0);
	
}

void afisare(){

	int i;
	nod *p;
	FILE *g = fopen("biconex.out", "w");
	fprintf(g,"%d\n",nrsol);
	memset(viz, 0 , sizeof(viz));
	
	for(i=1; i<=nrsol; i++){
		for(p = sol[i]; p != NULL; p = p->urm)
			viz[ p->inf ] = 0;
		
		for(p = sol[i]; p != NULL; p = p->urm)
			if( !viz[ p->inf ] )
				viz[p->inf] = 1, fprintf(g,"%d ",p->inf);
		
		fprintf(g,"\n");
	}
	
	fclose(g);
}

int main(){

	citire();
	solve();
	afisare();

	return 0;

}