Cod sursa(job #1883693)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 18 februarie 2017 10:11:17
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int st[100001];
int lst = 0, lrez = 0;
vector<int> rez[100001];
vector<int> g[100001];
int viz[100001], low[100001];
int n, m;

void dfs(int nod, int tnod)
{
	viz[nod] = viz[tnod] + 1;
	low[nod] = viz[nod];
	st[lst++] = nod;
	for (int i = 0; i < g[nod].size(); i++)
	{
		if (g[nod][i] != tnod)
		{
			if (!viz[g[nod][i]])
			{
				dfs(g[nod][i], nod);
				low[nod] = min(low[nod], low[g[nod][i]]);

				if (viz[nod] <= low[g[nod][i]])
				{
					while (lst > 0 && st[lst - 1] != g[nod][i])
					{
						lst--;
						rez[lrez].push_back(st[lst]);
					}
					lst--;
					rez[lrez].push_back(st[lst]);
					rez[lrez].push_back(nod);
					sort(rez[lrez].begin(), rez[lrez].end());
					lrez++;
				}
			}
			else low[nod] = min(low[nod], low[g[nod][i]]);
		}
	}
}

int main()
{
	int a, b;
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d", &a, &b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for (int i = 1; i <= n; i++)
	{
		if (!viz[i])
			dfs(i, 0);
	}
	printf("%d\n", lrez);
	for (int i = 0; i < lrez; i++)
	{
		for (int j = 0; j < rez[i].size(); j++)
		{
			printf("%d ", rez[i][j]);
		}
		printf("\n");
	}
	return 0;
}