Cod sursa(job #2722175)

Utilizator Iulia25Hosu Iulia Iulia25 Data 12 martie 2021 17:13:14
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream cin ("biconex.in");
ofstream cout ("biconex.out");

const int N = 1e5 + 5;

int n, m;
int nr_componente, nr_noduri, top;
int id[N], l[N], s[N];
vector <int> v[N], c[N];

void dfs(int nod) {
	id[nod] = l[nod] = ++nr_noduri;
	s[++top] = nod;
	for (auto it : v[nod])  {
		if (!id[it])  {
			dfs(it);
			l[nod] = min(l[nod], l[it]);
			if (l[it] == id[nod])  {
        ++nr_componente;
        while (s[top] != nod) {
          c[nr_componente].push_back(s[top]);
          --top;
        }
        c[nr_componente].push_back(nod);
      }
		} else  {
			l[nod] = min(l[nod], id[it]);
		}
	}
}

int main()  {
	cin >> n >> m;
	int x, y;
	for (int i = 1; i <= m; ++i)  {
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for (int i = 1; i <= n; ++i)  {
		if (!id[i]) {
			dfs(i);
		}
	}
	cout << nr_componente << '\n';
	for (int i = 1; i <= nr_componente; ++i)  {
    sort (c[i].begin(), c[i].end());
    for (auto it : c[i])
      cout << it << ' ';
    cout << '\n';
	}
	return 0;
}