Pagini recente » Cod sursa (job #660220) | Cod sursa (job #714711) | Cod sursa (job #3205374) | Cod sursa (job #2604522) | Cod sursa (job #2792596)
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m;
vector<int> la[100005];
int lowLink[100005];
int ids[100005];
int id = 0;
// cate comp biconexe sunt
int biconexe = 0;
// componenta conexa curenta
int cc = 0;
vector<vector<int>> res;
// comp conexe ramase dupa ce am eliminat muchile critice
vector<vector<int>> cc_dupa_mc;
struct hash_pair {
template <class T1, class T2>
size_t operator()(const pair<T1, T2>& p) const
{
auto hash1 = hash<T1>{}(p.first);
auto hash2 = hash<T2>{}(p.second);
return hash1 ^ hash2;
}
};
unordered_map<pair<int,int>,int,hash_pair> mc;
void dfs_critice(int s, int p)
{
lowLink[s] = id;
ids[s] = id;
id++;
for (auto el: la[s])
{
if (ids[el] == -1)
dfs_critice(el, s);
if (el != p)
lowLink[s] = min(lowLink[s], lowLink[el]);
}
if (lowLink[s] == ids[s] && p != -1)
{
mc[{s,p}] = 1;
mc[{p,s}] = 1;
biconexe ++;
res.push_back({s, p});
// adauga muchia de la s la p in mapu de muchi critice
// cout << s << ' ' << p << '\n';
}
}
void dfs(int s)
{
// cout << s << '\n';
cc_dupa_mc[cc].push_back(s);
ids[s] = cc;
for (auto el: la[s])
{
if (mc.find({s, el}) == mc.end() && mc.find({el, s}) == mc.end())
{
if (ids[el] == -1)
{
dfs(el);
}
}
}
}
int main()
{
f >> n >> m;
for (int i = 0; i < m; i++)
{
int x,y;
f >> x >> y;
la[x].push_back(y);
la[y].push_back(x);
}
for (int i = 1; i <= n; i++)
ids[i] = -1;
for (int i = 1; i <= n; i++)
{
if (ids[i] == -1)
dfs_critice(i, -1);
}
for (int i = 1; i<= n;i++)
ids[i] = -1;
for (int i = 1; i <= n; i++)
{
if (ids[i] == -1)
{
cc_dupa_mc.push_back(vector<int>());
dfs(i);
cc++;
}
}
for (auto& row: cc_dupa_mc)
{
if (row.size() > 1)
{
biconexe ++;
res.push_back(row);
}
}
g << biconexe << '\n';
for (auto& row: res)
{
if (row.size() == 1)
continue;
for (auto el: row)
g << el << ' ';
g << '\n';
}
return 0;
}