Pagini recente » Cod sursa (job #3356831) | Cod sursa (job #2398004) | Cod sursa (job #3332415) | Cod sursa (job #3343858) | Cod sursa (job #3352726)
//https://infoarena.ro/problema/biconex
//#ifdef _MSC_VER
// #define _CRT_SECURE_NO_WARNINGS
//#elif __GNUC__
// #pragma GCC optimize("Ofast,unroll-loops,inline")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#endif
//#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <utility>
#include <cstdint>
//#include <cstdio>
//#include <algorithm>
#include <vector>
//#include <array>
//#include <list>
//#include <forward_list>
//#include <string>
//#include <cstring>
//#include <cmath>
//#include <bitset>
//#include <queue>
#include <stack>
//#include <map>
//#include <set>
//#include <unordered_map>
//#include <unordered_set>
//#include <limits>
//#include <climits>
//#include <iomanip>
//#include <tuple>
//#include <numeric>
//#include <chrono>
//#include <memory>
using namespace std;
using int64 = int64_t;
using uint64 = uint64_t;
using int32 = int32_t;
using uint32 = uint32_t;
using int16 = int16_t;
using uint16 = uint16_t;
using pii = pair<int, int>;
using pll = pair<int64, int64>;
#define all(x) (x).begin(), (x).end()
#define allg(x) (x).begin(), (x).end(), greater<int>()
#define sz(x) (int)(x).size()
#define pb push_back
#define eb emplace_back
#define rfor(i, st, dr) for(auto i=(st); i<=(dr); ++i)
#define for0(i,n) for(auto i=0; i<(n); ++i)
#define rfor0(i,n) for(auto i=(n)-1; i>=0; --i)
#define for1(i,n) for(auto i=1; i<=(n); ++i)
#define rfor1(i,n) for(auto i=(n); i>=1; --i)
#define foreach(x,a) for(auto& x : a)
#define cforeach(x,a) for(const auto& x : a)
#define ft first
#define sd second
#define cendl cout << "\n"
#define fendl fout << "\n"
#define FASTIO ios::sync_with_stdio(false); cin.tie(nullptr);
//#define int int64
ifstream fin("biconex.in");
ofstream fout("biconex.out");
//FILE* fin = fopen("", "r");
//FILE* fout = fopen("", "w");
const int NRMAX = 100000;
vector<vector<int>> rez;
vector<int> gr[NRMAX + 5];
stack<int> st;
int low[NRMAX + 5], tmp[NRMAX + 5];
bool b[NRMAX + 5];
int timp = 0;
void dfs(int vf, int vfvf)
{
//cout << vf << " ";
++timp;
tmp[vf] = low[vf] = timp;
b[vf] = true;
for (int x : gr[vf])
{
if (x == vfvf) // daca muchie catre parinte
continue;
if (!b[x]) // nu mai am vizitat nodul x
{
st.push(x);
dfs(x, vf);
low[vf] = min(low[vf], low[x]);
// dupa ce am revenit
if (low[x] >= tmp[vf]) // formam o componenta biconexa
{
int* aux = new int[sz(st)];
int idx = 0;
// ne intorem
while (st.top() != x)
{
aux[idx++] = st.top();
st.pop();
}
aux[idx++] = st.top();
aux[idx++] = vf;
st.pop();
// adaugam nodurile din stiva in raspuns
rez.push_back(vector<int>(aux, aux + idx));
delete[] aux;
}
}
else // am mai vizitat nodul x
low[vf] = min(low[vf], tmp[x]); // am gasit un ciclu, deci actualizez low[vf]
}
}
int32 main()
{
//FASTIO;
int n, m, i;
fin >> n >> m;
while(m--)
{
int x, y;
fin >> x >> y;
gr[x].push_back(y);
gr[y].push_back(x);
}
//componente biconexe
for (i = 1; i <= n; ++i)
if (!b[i])
dfs(i, 0);
fout << sz(rez) << "\n";
cforeach(it, rez)
{
cforeach(x, it)
fout << x << " ";
fendl;
}
return 0;
}
/*
Cezar aici vorbeste singur, nu baga in seama :)
daca ne uitam la el ca un arbore
daca luam reper un nod
daca facem dfs pe el atunci vom avea muchi care is parcurse si unele care nu va mai fi nevoie sa le parcurgem
(adica cele care duc catre un nod vizitat)
daca nu e nevoie sa parcurgem o muchie insemna ca avem o componenta biconexa
*/