Cod sursa(job #1768209)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 30 septembrie 2016 15:19:03
Problema Componente biconexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>
#define mp make_pair
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define show(x) cerr << #x << " = " << x << "\n";
using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

const int NMAX = 200005;

int n,m,nr,fat[NMAX],niv[NMAX],nivmin[NMAX];
bool art[NMAX];
vector<int>v[NMAX],t[NMAX],comp[NMAX];
bitset<NMAX>viz;

void Dfs(int x)
{
	viz[x] = 1;
	niv[x] = niv[fat[x]] + 1;
	for (auto it : v[x])
		if (!viz[it])
		{
			fat[it] = x;
			t[x].pb(it);
			Dfs(it);
		}

	//check if it's articulation point
	int mn = 1<<30;
	for (auto it : t[x])
		mn = min(mn , nivmin[it]);

	if (t[x].size() && mn >= niv[x]) art[x] = 1;

	for (auto it : v[x])
		mn = min(mn , niv[it]);
	nivmin[x] = mn;
}

void Go(int x)
{
	comp[nr].pb(x);
	if (art[x] == 0)
		for (auto it : t[x])
			Go(it);
}

void Fill(int x)
{
	for (auto it : t[x])
	{
		nr++; comp[nr].pb(x);
		Go(it);
	}

}

int main()
{
	int i, x, y;

	fin >> n >> m;

	for (i = 1; i <= m; i++)
	{
		fin >> x >> y;
		v[x].pb(y);
		v[y].pb(x);
	}

	Dfs(1);
	if (t[1].size() > 1) art[1] = 1;

	for (i = 1; i <= n; i++)
		if (i == 1 || art[i] == 1)
			Fill(i);

	fout << nr << "\n";
	for (i = 1; i <= nr; i++)
		{
			for (auto it : comp[i])
				fout << it << " ";
			fout << "\n";
		}
	return  0;
}