Cod sursa(job #2185512)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 24 martie 2018 16:35:07
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int N = 100020;
vector <int> v[N], sol[N];
int nr, st, s[N], p[N], t[N];
int min(int a, int b)
{
	if (a > b)
		return a;
	return b;
}
void dfs(int nod) 
{
	s[++st] = nod;
	int m = v[nod].size();
	for (int i = 0; i<m; i++) 
	{
		int y = v[nod][i];
		if (p[y])
			p[nod] = min(p[nod], t[y]); 
		else 
		{
			int x = st;
			p[y] = t[y] = t[nod] + 1;
			dfs(y);
			p[nod] = min(p[y], p[nod]);
			if (p[y] >= t[nod]) 
			{
				sol[++nr].push_back(nod);
				while (x<st)
					sol[nr].push_back(s[st--]);
			}
		}
	}
}
int main() {
	int n, m, x, y;
	f >> n >> m;
	while (m--) 
	{
		f >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	t[1] = p[1] = 1;
	dfs(1);
	g << nr << '\n';
	for (int i = 1; i <= nr; i++) 
	{
		for (int j = 0; j<sol[i].size(); j++)
			g << sol[i][j] << ' ';
		g << '\n';
	}
}