Pagini recente » Cod sursa (job #372545) | Cod sursa (job #734602) | Cod sursa (job #1174660) | Cod sursa (job #396741) | Cod sursa (job #2884018)
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX = 1e5 + 5;
vector <int> g[NMAX];
int n, m, niv[NMAX], nivmin[NMAX];
void citire()
{
fin >> n >> m;
int i, j, a, b;
for(i = 1; i <= m; ++i)
{
fin >> a >> b;
g[a].pb(b);
g[b].pb(a);
}
}
bitset <NMAX> viz;
stack <int> stiva;
vector < vector <int> > sol;
vector <int> ax;
void dfs(int node, int fadir)
{
stiva.push(node);
viz[node] = 1;
nivmin[node] = niv[node] = niv[fadir] + 1;
for(auto &it: g[node])
{
if(it == fadir) continue;
if(viz[it]) {
nivmin[node] = min(nivmin[node], nivmin[it]);
continue;
}
dfs(it, node);
nivmin[node] = min(nivmin[node], nivmin[it]);
//nu pot merge mai sus, am componenta biconexa
if(nivmin[it] >= niv[node])
{
ax.clear();
while(!stiva.empty() && stiva.top() != it)
{
ax.push_back(stiva.top());
stiva.pop();
}
if(!stiva.empty() && stiva.top() == it)
{
ax.push_back(stiva.top());
stiva.pop();
}
ax.push_back(node);
sort(ax.begin(), ax.end());
sol.push_back(ax);
}
}
}
int main()
{
citire();
dfs(1, 0);
fout << sol.size() << '\n';
for(auto &it: sol)
{
for(auto &it2: it)
fout << it2 << ' ';
fout << '\n';
}
return 0;
}